3

有谁知道并行素数分解算法的方法是什么?

我不知道应该在算法的哪个阶段将其划分为线程。我如何以并行方式考虑素数分解?

考虑以下一个线程代码:

    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;
    }
4

1 回答 1

0

看起来这对于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) 开始并从那里开始而不是从一个开始,它可能会有更好的性能。

于 2013-05-08T13:54:52.337 回答