哪个是使用C++查找素数的最快算法？我使用筛选算法,但我仍然希望它更快!

实现此功能的最佳方式是什么:

ArrayList generatePrimes(int n)

此函数生成第一个n素数(编辑:where n>1),因此generatePrimes(5)将返回ArrayListwith {2, 3, 5, 7, 11}.(我在C#中这样做,但我很高兴Java实现 - 或任何其他类似的语言(所以不是Haskell)).

我知道怎么写这个函数,但是当我昨晚做到这一点时,它并没有像我希望的那样结束.这是我想出的:

ArrayList generatePrimes(int toGenerate)
{
    ArrayList primes = new ArrayList();
    primes.Add(2);
    primes.Add(3);
    while (primes.Count < toGenerate)
    {
        int nextPrime = (int)(primes[primes.Count - 1]) + 2;
        while (true)
        {
            bool isPrime = true;
            foreach (int n in primes)
            {
                if (nextPrime % n == 0)
                {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime)
            {
                break;
            }
            else
            {
                nextPrime …

我正在寻找一种实现或清晰的算法,用于在python,伪代码或其他任何可读的内容中获得N的素数因子分解.有一些要求/事实:

• N介于1到20位之间
• 没有预先计算的查找表,但是memoization很好.
• 不需要在数学上证明(例如,如果需要,可以依赖于Goldbach猜想)
• 不需要精确,如果需要,可以是概率/确定性的

我需要一个快速素数因子分解算法,不仅适用于自身,还适用于许多其他算法,如计算Euler phi(n).

我已经尝试了维基百科的其他算法,但要么我无法理解它们(ECM),要么我无法从算法(Pollard-Brent)创建工作实现.

我对Pollard-Brent算法非常感兴趣,因此对它的任何更多信息/实现都会非常好.

谢谢!

编辑

搞砸了一下后,我创建了一个非常快速的素数/分解模块.它结合了优化的试验分割算法,Pollard-Brent算法,米勒 - 拉宾素性测试和我在互联网上发现的最快的素数.gcd是常规Euclid的GCD实现(二进制Euclid的GCD 比常规GCD 慢得多).

赏金

哦,快乐,可以获得赏金!但我怎么能赢呢？

• 在我的模块中找到最优化或错误.
• 提供替代/更好的算法/实现.

最完整/最具建设性的答案得到了赏金.

最后模块本身:

import random

def primesbelow(N):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    #""" Input N>=6, Returns a list of primes, 2 <= p < N """
    correction = N % 6 > 1
    N = {0:N, 1:N-1, 2:N+4, 3:N+3, 4:N+2, 5:N+1}[N%6]
    sieve = [True] * (N // 3)
    sieve[0] = False
    for i in range(int(N …

我读了很多算法来找到素数,结论是如果数不能被前面的任何素数整除,那么数就是素数.

我无法找到更准确的定义.基于此,我编写了一个代码并且它表现令人满意,直到我传递的最大数量为1000000.但我相信有更快的算法来找到比给定数字更小的所有素数.

以下是我的代码,我可以有更好的版本吗？

 public static void main(String[] args) {
    for (int i = 2; i < 100000; i++) {
        if (checkMod(i)) {
            primes.add(i);
        }
    }
}

private static boolean checkMod( int num) {
    for (int i : primes){
        if( num % i == 0){
            return false;
        }
    }
    return true;
}