1

我试图在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)

4

8 回答 8

2

也许更复杂一点，但它到目前为止工作，它可能使用我在 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
于 2011-02-02T07:31:10.940 回答
1

问题是你的递归实现。用这个：

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;
}
于 2011-02-02T06:04:04.317 回答
1 
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;
}
于 2012-07-01T12:23:30.990 回答
0

好的！我想我已经解决了我的问题，除了 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,3forprimeFactors(81)和 5,3,2,2forprimeFactors(60)等等……

于 2011-02-02T16:25:55.840 回答
0 
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 ++;
            }
        }
    }
于 2013-07-09T18:49:39.713 回答
0 
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)));

}
于 2015-10-27T20:44:38.067 回答
-1

编辑：存在设计缺陷。为什么必须返回列表。它是在函数体之外定义的，并且会针对找到的每个因素进行更新。因此，无需退货。

于 2011-02-02T05:35:43.530 回答
-1

我的 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);
}
于 2013-07-22T01:50:38.303 回答