5

以下代码片段计算给定数字的素数：

public static LinkedList<Long> getPrimeFactors(Long number) {
    LinkedList<Long> primeFactors = new LinkedList<Long>();

    for (Long factor = Long.valueOf(2); factor <= number / factor; factor++) {
        if (number % factor == 0) {
            primeFactors.add(factor);
            while (number % factor == 0) {                  
                number /= factor;
            }
        }           
    }

    if (number > 1) {
        primeFactors.add(number);
    }

    return primeFactors;
}

计算 9223372036854775783 的素数需要 140937 毫秒（它是小于 的最后一个素数Long.MAX_VALUE）。有没有办法通过并发来实现这种分解，即使用ExecutorService？

编辑：

public static void getPrimeFactors(Long number) {
    LinkedList<Long> primeFactors = new LinkedList<Long>();

    if (number % 2 == 0) {
        primeFactors.add(2L);

        while (number % 2 == 0) {
            number /= 2;
        }
    }

    long limit = (long) Math.sqrt(number) + 1;

    ExecutorService service = Executors.newFixedThreadPool(2);
    LinkedList<Future<LinkedList<Long>>> futures = new LinkedList<Future<LinkedList<Long>>>();
    futures.add(service.submit(new PrimeFactor(3, limit / 2, number)));
    futures.add(service.submit(new PrimeFactor(1 + limit / 2, limit, number)));

    for (Future<LinkedList<Long>> future : futures) {
        try {
            primeFactors.addAll(future.get());
        } catch (InterruptedException e) {
            e.printStackTrace();
        } catch (ExecutionException e) {
            e.printStackTrace();
        }
    }
    service.shutdown();

    if(number>1) {
        primeFactors.add(number);           
    }

    System.out.println(primeFactors);
}

private static class PrimeFactor implements Callable<LinkedList<Long>> {
    private long lowerLimit;
    private long upperLimit;
    private Long number;

    public PrimeFactor(long lowerLimit, long upperLimit, Long number) {
        this.lowerLimit = lowerLimit;
        this.upperLimit = upperLimit;
        this.number = number;
    }

    public LinkedList<Long> call() throws Exception {
        LinkedList<Long> primeFactors = new LinkedList<Long>();
        for (long i = lowerLimit; i < upperLimit; i += 2) {
            if (number % i == 0) {
                primeFactors.add(i);
                while (number % 2 == 0) {
                    number /= i;
                }
            }
        }
        return primeFactors;
    }

}

第二次编辑：

public static LinkedList<Long> getPrimeFactorsByFastGeneralMethod(long number) {
    LinkedList<Long> primeFactors = new LinkedList<Long>();

    if (number % 2 == 0) {
        primeFactors.add(2L);

        while (number % 2 == 0) {
            number /= 2;
        }
    }

    long limit = (long) Math.sqrt(number);

    for (long factor = 3; factor <= limit; factor += 2) {
        if (number % factor == 0) {
            primeFactors.add(factor);
            while (number % factor == 0) {
                number /= factor;
            }
        }
    }

    if (number > 1) {
        primeFactors.add(number);
    }

    return primeFactors;
}

现在代码片段：

    LinkedList<Long> primeFactors = Factorization.getPrimeFactorsByConcurrentGeneralMethod(600851475143L);
    System.out.println("Result: " + primeFactors.get(primeFactors.size() - 1));

    primeFactors = Factorization.getPrimeFactorsByFastGeneralMethod(600851475143L);
    System.out.println("Result: " + primeFactors.get(primeFactors.size() - 1));

正在给出输出：

Result: 600851475143
Result: 6857

注意：类名是Factorization，我把方法名改成getPrimeFactors了getPrimeFactorsByConcurrentGeneralMethod

4

3 回答 3

6

嗯，在你开始考虑并发实现之前，我建议稍微优化一下算法。除了 2 之外，每个素数都是奇数，因此将 2 设为特殊情况，然后从 3 开始使用循环并将因子增加 2。然后不是计算每个循环结束的数字/因子（这也使得 JIT 的优化更难我认为) 只计算一次 Sqrt(N) - 毕竟我们知道每个数字只能有一个素因子 > sqrt(N) ;)

如果你这样做了，我会改变你的方法签名，这样你就不会总是从 3 开始并一直工作到 Sqrt(N)，而是给它开始和结束范围。最简单的解决方案是将范围从 3-Sqrt(N) 拆分为 K 个部分，其中 K 是可用的内核数（因为这不是真正平衡的，使用较小的部分可能会给您带来更好的负载平衡）并将其放入刽子手服务。然后，您只需收集所有结果并从所有较小的列表中创建一个列表。

请注意，这种简单的方法对 BigIntegers 有更多的工作，因为您总是计算起始编号上的值，并且每个除法算法的复杂性取决于位大小 - 如果您使用较小的作业大小并在它们之间进行同步，您也可以解决这个问题。

PS：请注意，您的分割范围算法仍然必须正确处理案例 2 和 sqrt(n)。

PPS：我希望您知道这个问题存在于 NP 中，您这样做只是为了了解一点并发性。

于 2011-06-26T13:52:45.643 回答
1

不，没有这样简单的方法，至少是已知的一种。最优整数因式分解的问题在数学中仍然悬而未决。

您可以使用椭圆曲线法 (ECM) Prime Factorization。它非常适合并行计算。但方法本身并不简单——几千行代码。来源可用，例如here

于 2011-06-26T14:48:51.773 回答
0

您可以通过某些方式调整您的实现：

  1. 正如 Christian Semrau 在他的评论中已经提到的那样，避免不必要的自动装箱。
  2. 为“简单”案例创建一个快捷方式，例如，您遍历 2 和 number/2 之间的每个数字。这是不必要的，因为 2 是唯一的偶数因数。在最好的情况下，您将使用此快捷方式节省一半的迭代次数。
  3. 您不需要计算 的主要因素number，sqrt(number)就足够了。

  4. 整数分解有更有效的方法

    public static List<Long> getPrimeFactors(long number) {
    List<Long> primeFactors = new ArrayList<Long>();

    // Only process natural numbers
    if(number < 1l) {
        return primeFactors;
    }

    // The only prime factor of 1 is 1
    if(number == 1l) {
        primeFactors.add(1l);
        return primeFactors;
    }

    // Even have the prime factor 2
    if(number % 2l == 0l) {
        primeFactors.add(2l);

        while(number % 2l == 0l) {
            number /= 2l;
        }
    }

    // Iterate from 3 to sqrt(number) to calculate the remaining prime factors
    for (long factor = 3l; factor < Math.sqrt(number); factor+=2l) {
        if (number % factor == 0) {
            primeFactors.add(factor);
            while (number % factor == 0) {                  
                number /= factor;
            }
        }           
    }

    if (number > 1) {
        primeFactors.add(number);
    }

    return primeFactors;
}
于 2011-06-26T14:09:22.330 回答