java - 并行素因数分解

Question

这个问题已经有答案了:

Parallel Algorithms for Generating Prime Numbers (possibly using Hadoop's map reduce) (1 个回答)

已关闭 10 年前。

有人知道并行素因数分解算法的方法是什么吗？

我不知道应该在算法的哪个阶段将其划分为线程..我如何以并行方式思考质因数分解？

考虑以下一个线程代码:

    public static void  primeFactorization(ArrayList<Integer> factors, int num){
        //factors is an array to save the factorization elements
        //num is the number to be factorized 
        int limit = num/2+1;

        if(isPrime(num))
            factors.add(num);

        else{
            while(num%2==0){
                factors.add(2);
                num=num/2;
            }

           for (int i=3; i<limit; i+=2){
               while (isPrime(i) && num%i==0){
                   factors.add(i);
                    num = num/i;
               }
           }
       }
    }

    private static boolean isPrime(int x) {
          int top = (int)Math.sqrt(x);
          for (int i = 2; i <= top; i++)
             if ( x % i == 0 )
                return false;
          return true;
    }

Answer 1

看来这对于 Fork/Join Framework 来说确实是一个很好的用途。 。看来您应该能够通过递归传递您找到的新因素来使用它。尝试看一下 RecursiveAction以及。在伪代码中，您应该能够执行如下操作:

public void getFactors(List<Integer> factors, int num){
    if(you can find a factor){
        add the two factors to the pool to be factored further
    }
    else{
        factors.add(num);
    }  
}

顺便说一句，如果您从中间 (num/2) 开始并从那里开始，而不是从 1 开始，它可能会有更好的性能。