Алгоритм рекурсивного простого фактора в Java
Я пытаюсь реализовать простой алгоритм в 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)
8 ответов
ХОРОШО! Я думаю, что решил свою проблему, за исключением того факта, что 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) и так далее...
Возможно, немного сложнее, но он работает до сих пор и использует, вероятно, самый быстрый (и самый маленький) генератор простых чисел, который я мог найти в 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
Проблема в вашей рекурсивной реализации. использовать этот:
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;
}
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;
}
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)));
}
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 ++;
}
}
}
Моя 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);
}
Изменить: Существует недостаток дизайна. Почему вы должны вернуть список. Он определяется вне тела функции и будет обновляться для каждого найденного фактора. Поэтому возвращать его не нужно.