前10000个质数最有效的代码？
我想打印前10000个质数。
谁能给我最有效的代码吗？
说明：
代码对于n> 10000而言效率是否低并不重要。代码的大小无关紧要。我们不能仅以任何方式对值进行硬编码。
解决方案：
Atkin筛子可能是我们正在寻找的筛子，其上限运行时间为O(N / log log N)。
如果只将数字1加1而不是6的倍数，则运行速度可能会更快，因为所有高于3的质数都与6的某个倍数相差1.
我的陈述的资源
根本没有效率，但是我们可以使用正则表达式测试素数。
/^1?$|^(11+?)+$/
这对于由k个1''组成的字符串测试k是否不是质数(即该字符串是由一个''1''还是可以表示为n元乘积的任意数量的''1s组成)。
我修改了在CodeProject上找到的代码以创建以下代码：
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;
}
}
if(divisible == false) {
primeNumbers.Add(i);
Console.Write(i + " ");
}
}
在我的ASP.NET Server上对其进行测试花费了大约1分钟的时间。
我推荐一个筛子，或者是Eratosthenes筛子，或者是Atkin筛子。
筛子或者Eratosthenes可能是查找素数列表的最直观方法。基本上，我们：
写下一个从2到我们想要的任何限制的数字列表，比如说1000。取第一个未被舍去的数字(第一次迭代是2)，然后从列表中舍去该数字的所有倍数。重复步骤2，直到到达列表的末尾。所有未划掉的数字都是质数。
显然，可以做很多优化来使该算法更快地工作，但这是基本思想。
Atkin的筛子使用类似的方法，但不幸的是，我对它的了解不足，无法向我们解释。但是我确实知道，我链接的算法需要8秒钟才能弄清在古老的Pentium II-350上所有的质数达到1000000000
Eratosthenes筛网源代码：http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/
阿特金筛子源代码：http://cr.yp.to/primegen.html
Eratosthenes的筛子是必经之路，因为它既简单又快速。我在C中的实现
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
int main(void)
{
unsigned int lim, i, j;
printf("Find primes upto: ");
scanf("%d", &lim);
lim += 1;
bool *primes = calloc(lim, sizeof(bool));
unsigned int sqrtlim = sqrt(lim);
for (i = 2; i <= sqrtlim; i++)
if (!primes[i])
for (j = i * i; j < lim; j += i)
primes[j] = true;
printf("\nListing prime numbers between 2 and %d:\n\n", lim - 1);
for (i = 2; i < lim; i++)
if (!primes[i])
printf("%d\n", i);
return 0;
}
找到质数的CPU时间(在Pentium Dual Core E2140 1.6 GHz上，使用单核)
~ 4s for lim = 100,000,000
GateKiller，如何在foreach循环中的if中添加一个break呢？这将大大加快速度，因为如果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 + " ");
}
}
使用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。
这并不严格反对硬编码限制，但是非常接近。为什么不以编程方式下载此列表并打印出来呢？
http://primes.utm.edu/lists/small/10000.txt
@Matt：log(log(10000))为〜2
摘自Wikipedia文章(我们引用过)Atkin的Sieve：
This sieve computes primes up to N using O(N/log log N) operations with only N1/2+o(1) bits of memory. That is a little better than the sieve of Eratosthenes which uses O(N) operations and O(N1/2(log log N)/log N) bits of memory (A.O.L. Atkin, D.J. Bernstein, 2004). These asymptotic computational complexities include simple optimizations, such as wheel factorization, and splitting the computation to smaller blocks.
给定沿O(N)(对于Eratosthenes)和O(N / log(log(N())))(对于Atkin)的渐近计算复杂度，我们不能说(对于较小的N = 10_000)哪种算法如果实施将会更快。
阿奇姆·弗拉门坎普(Achim Flammenkamp)在Eratosthenes的《筛子》(The Sieve of Eratosthenes)中写道：
被引用：
@ num1
For intervals larger about 10^9, surely for those > 10^10, the Sieve of Eratosthenes is outperformed by the Sieve of Atkins and Bernstein which uses irreducible binary quadratic forms. See their paper for background informations as well as paragraph 5 of W. Galway's Ph.D. thesis.
因此，对于" 10_000"而言，Eratosthenes的筛子可能比Atkin的筛子快。
要回答OP，代码是prime_sieve.c(由num1引用)
根据GateKiller的改编和后续内容，这是我使用的最终版本。
public IEnumerable<long> PrimeNumbers(long number)
{
List<long> primes = new List<long>();
for (int i = 2; primes.Count < number; i++)
{
bool divisible = false;
foreach (int num in primes)
{
if (i % num == 0)
divisible = true;
if (num > Math.Sqrt(i))
break;
}
if (divisible == false)
primes.Add(i);
}
return primes;
}
基本上是相同的，但是我添加了" Sqrt中断"的建议，并更改了一些变量以使其更适合我。 (我正在研究Euler，并且需要第10001个素数)
筛子似乎是错误的答案。筛子给质数最多为N，而不是前N个质数。运行@Imran或者@Andrew Szeto，我们可以得到最多为N的素数。
如果我们不断尝试筛选越来越大的数字，直到我们达到结果集的一定大小，并使用一些已经获得的数字缓存，则该筛子可能仍然可用，但是我相信它不会比@ Pat''s这样的## 解决方案快。
这是几天前我在PowerShell中编写的Eratosthenes筛子。它具有一个参数，用于标识应返回的素数的数量。
#
# generate a list of primes up to a specific target using a sieve of eratosthenes
#
function getPrimes { #sieve of eratosthenes, http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
param ($target,$count = 0)
$sieveBound = [math]::ceiling(( $target - 1 ) / 2) #not storing evens so count is lower than $target
$sieve = @($false) * $sieveBound
$crossLimit = [math]::ceiling(( [math]::sqrt($target) - 1 ) / 2)
for ($i = 1; $i -le $crossLimit; $i ++) {
if ($sieve[$i] -eq $false) {
$prime = 2 * $i + 1
write-debug "Found: $prime"
for ($x = 2 * $i * ( $i + 1 ); $x -lt $sieveBound; $x += 2 * $i + 1) {
$sieve[$x] = $true
}
}
}
$primes = @(2)
for ($i = 1; $i -le $sieveBound; $i ++) {
if($count -gt 0 -and $primes.length -ge $count) {
break;
}
if($sieve[$i] -eq $false) {
$prime = 2 * $i + 1
write-debug "Output: $prime"
$primes += $prime
}
}
return $primes
}
在Python中
import gmpy
p=1
for i in range(10000):
p=gmpy.next_prime(p)
print p
我刚刚开始学习它时就使用python编写了它，并且效果很好。此代码生成的第10,000个素数与http://primes.utm.edu/lists/small/10000.txt中提到的相同。要检查n是否为质数，请将n除以2到sqrt(n)之间的数字。如果该数字范围中的任何一个均完美地除以n，则它不是质数。
import math
print ("You want prime till which number??")
a = input()
a = int(a)
x = 0
x = int(x)
count = 1
print("2 is prime number")
for c in range(3,a+1):
b = math.sqrt(c)
b = int(b)
x = 0
for b in range(2,b+1):
e = c % b
e = int(e)
if (e == 0):
x = x+1
if (x == 0):
print("%d is prime number" % c)
count = count + 1
print("Total number of prime till %d is %d" % (a,count))
