Алгоритм рекурсивного простого фактора в Java

Question

Я пытаюсь реализовать простой алгоритм в Java для нахождения всех простых чисел факторов целого числа, переданного параметром:

private static ArrayList<Integer> lstPrime= new ArrayList<Integer>();

    public static ArrayList primeFactors(int n) {

        if (isPrime(n)) 
        {
            lstPrime.add(n);
        }

        for (int i=2; i<=(Math.sqrt(n)); i++)
        {
            if (n % i == 0)
            {
                lstPrime.addAll(primeFactors(n/i));
                return lstPrime;
            }
        }
        return lstPrime;
    }

Забавно, что если я передам 81 как n, результат будет: 3, 3, 3, 3, 3, 3, 3, 3, тогда как ДОЛЖЕН быть: 3, 3, 3, 3 (3 ^ 4 = 81)

Answer 1

Возможно, немного сложнее, но он работает до сих пор и использует, вероятно, самый быстрый (и самый маленький) генератор простых чисел, который я мог найти в Java.

Сначала мы получили генератор простых чисел, необходимый для проверки, является ли значение простым. Мы используем генератор (этот в 10 раз быстрее, чем простой метод), поэтому мы используем кэшированный список:

/**
 * Sieve of Sundaram prime number generator
 * Implementation following the Sieve of Sundaram to generate prime numbers 
 * 
 * @see http://en.wikipedia.org/wiki/Sieve_of_Sundaram
 */
static public class SundaramSievePrimeGenerator {
   public String getName() { return "Sieve of Sundaram generator"; }
   public int[] findPrimes(int max) {
      int n = max/2;
      boolean[] isPrime = new boolean[max];

      Arrays.fill(isPrime, true);

      for (int i=1; i<n; i++) {
         for (int j=i; j<=(n-i)/(2*i+1); j++) {
            isPrime[i+j+2*i*j] = false;
         }
      }

      int[] primes = new int[max];
      int found = 0;
      if (max > 2) {
         primes[found++] = 2;
      }
      for (int i=1; i<n; i++) {
         if (isPrime[i]) {
            primes[found++] = i*2+1;
         }
      }

      return Arrays.copyOf(primes, found);
   }
}

Тогда у нас есть два метода, необходимых для фактического получения списка простых множителей для n:

/**
 * Reuse an instance of the SundaramSievePrimeGenerator
 */
static public List<Integer> findPrimeFactors(int n, SundaramSievePrimeGenerator g) {
   ArrayList<Integer> primeFactors = new ArrayList<Integer>();

   int[] primes = g.findPrimes(n+1);
   int v;

   // debug
   //System.out.print("** primes found : ");
   //for (int a : primes) {
   //   System.out.print(" " + a);
   //}
   //System.out.println();

   if (primes[primes.length-1] == n) {
      primeFactors.add(n);
   } else {

      int max = primes.length - 1;

      for (int i=max; i>=0; i--) {
         primeFactors.add(primes[i]);
         if (testPrimeFactor(n, primes[i], primes, i, primeFactors)) {
            break;  // we found our solution
         }
         primeFactors.clear();
      }
   }

   return primeFactors;
}

/**
 * Recursive method initially called by findPrimeFactors(n, g)
 */
static private boolean testPrimeFactor(int n, int v, int[] primes, int index, List<Integer> factors) {
   int v2 = v * primes[index];

   if (v2 == n) {
      factors.add(primes[index]);
      return true;
   } else if (v2 > n) {
      if (index > 0) {
         return testPrimeFactor(n, v, primes, index-1, factors);
      } else {
         return false;
      }
   } else {
      while (index > 0) {
         factors.add(primes[index]);

         if (testPrimeFactor(n, v2, primes, index, factors)) {
            return true;
         }

         factors.remove(factors.size()-1);   // no good, remove added prime
         v2 = v * primes[--index];
      }
      return false;   // at this point, we are still below n... so no good
   }
}

И, наконец, наш тестовый пример:

int n = 1025;
SundaramSievePrimeGenerator generator = new SundaramSievePrimeGenerator();

List<Integer> factors = findPrimeFactors(n, generator);

if (factors.isEmpty()) {
   System.out.println("No prime factors found for " + n);
} else {
   System.out.println(n + " is composed of " + factors.size() + " prime factors");
   int v = 1;
   for (int i : factors) {
      v *= i;
      System.out.print(" " + i);
   }
   System.out.println(" = " + v);
}

Например, этот код выше выдаст:

1025 is composed of 3 prime factors
 41 5 5 = 1025

И изменение n = 81 даст желаемый результат

81 is composed of 4 prime factors
 3 3 3 3 = 81

Answer 2

public static void primeFactorsOf( int n ) 
{
    int i;

    if( isPrime( n ) )
        System.out.println( n +". " );
    else
    {
        for( i = 2; i < n; i ++ )
        {
            if( isPrime( i ) && n % i == 0 )
            {
                System.out.print( i +", " );
                n = n/i;
                primeFactorsOf( n );
            }
        }
    }
}

public static boolean isPrime( int n )
{
    int i;

    if( n < 2 )
        return false;
    else
    {
        for( i = 2; i < n; i += 1 )
        {
            if( n % i == 0 ) 
                return false;
        }
    }    

    return true;
}

Answer 3

проблема в вашей рекурсивной реализации. используйте это:

public static ArrayList primeFactors(int n){
    if (isPrime(n))
    {
        list.add(n);
        return list;
    }
    int i = 1;
    while(true){
        if (n % (i+=2) == 0){
            if (isPrime(i))
            {
                n = n / i;
                list.add(i);
                i = 1;
            }
        }
        if (i> Math.sqrt(n))
            break;
    }
    list.add(n);
    return list;
}

Answer 4

public static String soNguyenTo(int x, int i) {
    if (i == 1 && x > 1) {
        return "là số nguyen tố";
    }
    if (x == 0 || x % i == 0) {
        return "không phải là số nguyên tố";
    } else {
        return soNguyenTo(x, i - 1);
    }
}

public static void main(String[] args) {
    input = new Scanner(System.in);
    System.out.println("nhập số bất kỳ");
    int i = input.nextInt();
    System.out.println(i + ": " + soNguyenTo(i, (int) Math.sqrt(i)));

}

Answer 5

Моя Java ржавая, поэтому вам придется самостоятельно добавлять массивы / списки / векторы, но пока это кажется проще, чем во всех других решениях.

public static void primeFactors(int n) 
{
  for (int i = 2; i < n; i++)
    if (n % i == 0)
    {
      primeFactors(n / i);
      primeFactors(i);
    }

  System.out.println(n);
}

Answer 6

public static void primeFactorsOf( int n )
    {
        int i = 2;
        boolean isFactor = false;

        if( isPrime( n ) )
            System.out.println( n+"." );
        else 
        {
            while( !isFactor )
            {
                if( ( n % i == 0 ) && ( isPrime( i ) ) )
                {
                    System.out.print( i +", " );
                    primeFactorsOf( n / i );
                    isFactor = true;
                }
                else
                    i ++;
            }
        }
    }

Answer 7

OK!Я думаю, что я решил свою проблему, за исключением того факта, что ArrayList объявлен вне рекурсивной функции.Я не могу представить никакой другой способ обработки списка, поскольку, поскольку это рекурсивная функция, если список будет объявлен внутри функции, он будет создаваться снова и снова каждый раз, когда происходит рекурсия.Вот что я имею до сих пор, не стесняйтесь критиковать:

public static ArrayList<Integer> list = new ArrayList<Integer>();

public static void primeFactors(int n) {
    if (isPrime(n)) 
    {
        list.add(n);
        return;
    }

    int i = 2;
    while (i < n/2)
    {
        if (n % i == 0)
        {
             if (isPrime(i))
             {
                 primeFactors(n/i);
                 list.add(i);
                 return;
             } 
        }
        i++;
    }
    return;
}

Например, этот код будет выдавать: 3,3,3,3 для primeFactors(81) и 5,3,2,2 для primeFactors(60) и так далее ...

Answer 8

Edit: Есть недостаток дизайна. Почему вы должны вернуть список. Он определен вне тела функции и будет обновляться для каждого найденного фактора. Поэтому возвращать его не нужно.