前10000个素数最有效的代码?

Niyaz 53 algorithm performance primes

我想打印前10000个素数.任何人都可以给我最有效的代码吗?澄清:

  1. 如果你的代码在n> 10000时效率低下并不重要.
  2. 代码的大小无关紧要.
  3. 您不能以任何方式对值进行硬编码.

Matt.. 47

Atkin的Sieve可能就是您正在寻找的,它的上限运行时间是O(N/log log N).

如果你只运行数字1和1比6的倍数少,它可能会更快,因为3以上的所有素数都是1,远离6的倍数. 我的陈述的资源

  • 虽然这是一个很好的答案,但Sieves只生成[2,N]范围内的素数,而不是*前N个素数*. (6认同)
  • 由于这被标记为'回答':-1,当OP想要效率为10000的小固定n时,谈论渐近线.1.用于链接Atkin的Sieve而不用浏览它:文章本身提到Atkin只是*渐近*优于Eratosthenes,但在实践中,如果在实施上花费相同的努力,它总是更慢; 对于OP的问题,Eratosthenes的代码更简单,速度提高了几个数量级.关于mod 6车轮的评论没有多大意义:Atkin已经基于mod 30车轮,所以没有办法用较小的车轮加速它. (5认同)
  • 对于小N来说,Eratosthenes的筛子会更快.看到我的答案. (3认同)

num1.. 37

我建议筛子,要么埃拉托色尼的筛阿特金的筛.

筛子或Eratosthenes可能是找到素数列表的最直观的方法.基本上你:

  1. 记下从2到你想要的任何限制的数字列表,比方说1000.
  2. 取第一个未被划掉的数字(对于第一次迭代,这是2)并从列表中除去该数字的所有倍数.
  3. 重复步骤2,直到到达列表末尾.所有未被划掉的数字都是素数.

显然,可以做很多优化来使这个算法更快地工作,但这是基本的想法.

阿特金的筛子采用了类似的方法,但不幸的是,我不太了解它给你解释.但我知道我链接的算法需要8秒才能计算出古代奔腾II-350上的所有素数高达1000000000

Eratosthenes筛选源代码:http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/

Siekin of Atkin源代码:http://cr.yp.to/primegen.html


John with wa.. 18

这并不严格违反硬编码限制,但非常接近.为什么不以编程方式下载此列表并将其打印出来呢?

http://primes.utm.edu/lists/small/10000.txt

  • "筛选谷歌" (44认同)
  • 对于大多数计算机,计算值将比通过Internet下载它们所涉及的延迟更快. (14认同)
  • 哈哈@krog.你为什么每次都费心去建立一个网络连接和所有爵士乐到DL的静态文件?当然你要预先下载它,哎呀,甚至把它硬编码成阵列. (7认同)
  • 但不是从内存中准备好列表.这可能就是他的意思. (3认同)

palotasb.. 12

GateKiller,如何添加一个breakifforeach循环?这会加速很多事情,因为如果像6可以被2整除,你就不需要用3和5来检查.(如果我有足够的声誉,我会投票你的解决方案:-) ......)

ArrayList primeNumbers = new ArrayList();

for(int i = 2; primeNumbers.Count < 10000; i++) {
    bool divisible = false;

    foreach(int number in primeNumbers) {
        if(i % number == 0) {
            divisible = true;
            break;
        }
    }

    if(divisible == false) {
        primeNumbers.Add(i);
        Console.Write(i + " ");
    }
}


Will Ness.. 11

在Haskell中,我们几乎可以逐字逐句地写下Eratosthenes筛子的数学定义," 素数是1以上的自然数,没有任何复合数,其中复合物是通过枚举每个素数的倍数得到的 ":

primes = 2 : minus [3..] (foldr (\p r -> p*p : union [p*p+p, p*p+2*p..] r)
                                [] primes)

primes !! 10000 几乎是瞬间的.

参考文献:


上面的代码很容易调整为仅在赔率上工作primes = 2 : 3 : minus [5,7..] (foldr (\p r -> p*p : union [p*p+2*p, p*p+4*p..] r) [] (tail primes)).通过在树状结构中折叠,时间复杂度得到了很大改善(仅大约高于最佳的对因子),并且通过多级素数生产大大提高了空间复杂度,

primes = 2 : _Y ( (3:) . sieve 5 . _U . map (\p -> [p*p, p*p+2*p..]) )
  where
    _Y g = g (_Y g)                        -- non-sharing fixpoint combinator
    _U ((x:xs):t) = x : (union xs . _U . pairs) t       -- ~= nub.sort.concat
    pairs    (xs:ys:t)  = union xs ys : pairs t
    sieve k s@(x:xs) | k < x      = k : sieve (k+2) s   -- ~= [k,k+2..]\\s,
                     | otherwise  =     sieve (k+2) xs  --   when s?[k,k+2..]

(在Haskell中,括号用于分组,函数调用仅通过并置来表示,(:)是列表的cons运算符,并且(.)是函数式合成运算符:) (f . g) x = (\y -> f (g y)) x = f (g x).


jfs.. 10

@Matt:log(log(10000))是~2

来自维基百科的文章(你引用的)阿特金筛选:

该筛子使用O(N/log log N)仅具有N 1/2个o(1)位存储器的操作来计算高达N的质数.这比使用O(N) 操作和O(N 1/2(log log N)/ log N)位存储器的Eratosthenes筛网好一点(AOL Atkin,DJ Bernstein,2004).这些渐近计算复杂性包括简单优化,例如车轮分解,以及将计算分成较小的块.

给定O(N)(对于Eratosthenes)和O(N/log(log(N)))(对于Atkin)的渐近计算复杂性,我们不能说(对于小N=10_000)如果实现哪个算法将更快.

Achim Flammenkamp在Eratosthenes的筛选中写道:

被引用:

@ NUM1

对于大于10 ^ 9的区间,对于那些> 10 ^ 10的区间,Eratosthenes的筛子的表现优于使用不可约二元二次型的阿特金斯和伯恩斯坦的筛子.请参阅他们的论文了解背景信息以及W. Galway博士的第5段.论文.

因此10_000,Eratosthenes的Sieve可以比Atkin的Sieve更快.

要回答OP代码是prime_sieve.c(引用num1)


hoyhoy.. 7

使用GMP,可以编写以下内容:

#include <stdio.h>
#include <gmp.h>

int main() {
  mpz_t prime;
  mpz_init(prime);
  mpz_set_ui(prime, 1);
  int i;
  char* num = malloc(4000);
  for(i=0; i<10000; i++) {
    mpz_nextprime(prime, prime);
    printf("%s, ", mpz_get_str(NULL,10,prime));
  }
}

在我的2.33GHz Macbook Pro上,它执行如下:

time ./a.out > /dev/null

real    0m0.033s
user    0m0.029s
sys    0m0.003s

在同一台笔记本电脑上计算1,000,000个素数:

time ./a.out > /dev/null

real    0m14.824s
user    0m14.606s
sys     0m0.086s

GMP针对此类事物进行了高度优化.除非您真的想通过编写自己的算法来理解算法,否则建议您在C下使用libGMP.


engtech.. 5

根本不高效,但您可以使用正则表达式来测试素数.

/^1?$|^(11+?)\1+$/

这测试对于由k " 1" 组成的字符串,k是否不是素数(即该字符串是否由一个" 1"或任何数量的1"s"组成,可以表示为n元产品).