我想打印前10000个质数。
谁能给我最有效的代码吗？
说明：
您的代码对于n> 10000效率是否低并不重要。
代码的大小无关紧要。
您不能仅以任何方式对值进行硬编码。
Atkin筛子可能是您正在寻找的筛子，其上限运行时间为O(N / log log N)。
如果只运行数字1而不是6的倍数，则数字1可能会更快，因为3之上的所有质数都与6的某个倍数相距1。
我的陈述的资源
我推荐一个筛子，要么是Eratosthenes筛子，要么是Atkin筛子。
筛子或Eratosthenes可能是查找素数列表的最直观方法。基本上，您：
写下一个数字列表，从2到您想要的任何限制(例如1000)。
取第一个未被舍去的数字(对于第一次迭代，为2)，并从列表中舍去该数字的所有倍数。
重复步骤2，直到到达列表的末尾。所有未划掉的数字都是质数。
显然，可以做很多优化来使该算法更快地工作，但这是基本思想。
Atkin的筛子使用类似的方法，但是不幸的是，我对它的了解不足，无法向您解释。但是我确实知道，我链接的算法需要8秒钟才能弄清在古老的Pentium II-350上所有的质数达到1000000000
筛网筛网源代码：http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/
阿特金筛子源代码：http://cr.yp.to/primegen.html
这并不严格反对硬编码限制，但是非常接近。为什么不以编程方式下载此列表并打印出来呢？
http://primes.utm.edu/lists/small/10000.txt
GateKiller，如何将break添加到foreach循环中的if？这将大大加快处理速度，因为如果6被2整除，则您无需检查3和5。(如果我有足够的声誉，我还是会投票给您的解决方案:-) ...)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 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 +"");
}
} |
在Haskell中，我们几乎可以逐字写下Eratosthenes筛子的数学定义，"素数是大于1的自然数，没有任何合成数，其中的合成是通过枚举每个素数的倍数来找到的"：
1
2
3
4
| import Data.List.Ordered (minus, union)
primes = 2 : minus [3..] (foldr (\p r -> p*p : union [p*p+p, p*p+2*p..] r)
[] primes) |
primes !! 10000几乎是瞬时的。
参考文献：
-
Eratosthenes筛
-
理查德·伯德的筛子(请参阅第10,11页)
-
减，联合
上面的代码很容易调整为仅在赔率上工作，primes = 2 : 3 : minus [5,7..] (foldr (\p r -> p*p : union [p*p+2*p, p*p+4*p..] r) [] (tail primes))。通过折叠成树状结构，时间复杂度大大提高(大约比最佳对数高)，而在
1
2
3
4
5
6
7
| 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))。
@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筛子中写道：
被引用：
@ 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引用)
使用GMP，可以编写以下代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| #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上，它执行如下：
1
2
3
4
5
| time ./a.out > /dev/null
real 0m0.033s
user 0m0.029s
sys 0m0.003s |
在同一台笔记本电脑上计算1,000,000个素数：
1
2
3
4
5
| time ./a.out > /dev/null
real 0m14.824s
user 0m14.606s
sys 0m0.086s |
GMP已针对此类情况进行了高度优化。除非您真的想通过编写自己的算法来理解算法，否则建议您在C语言下使用libGMP。
根本没有效率，但是您可以使用正则表达式测试素数。
对于由k个" 1"组成的字符串，此测试是否k不是质数(即，该字符串是否由一个" 1"或任意数量的" 1"组成，可以表示为n元产品)。
我修改了在CodeProject上找到的代码以创建以下代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 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的筛子是必经之路，因为它既简单又快速。我在C中的实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #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("
Listing prime numbers between 2 and %d:
", lim - 1);
for (i = 2; i < lim; i++)
if (!primes[i])
printf("%d
", i);
return 0;
} |
找到质数的CPU时间(在Pentium Dual Core E2140 1.6 GHz上，使用单核)
~ 4s for lim = 100,000,000
这是几天前我在PowerShell中编写的Eratosthenes筛。它具有一个参数，用于标识应返回的素数的数量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| #
# 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中
1
2
3
4
5
| import gmpy
p=1
for i in range(10000):
p=gmpy.next_prime(p)
print p |
BenGoldberg提到的deque sieve算法值得一看，不仅因为它非常优雅，而且因为它有时在实践中可能有用(与Atkin的Sieve不同，这纯粹是一种学术练习)。
好。
deque sieve算法的基本思想是使用一个小的滑动筛子，该筛子足够大，可以为每个当前"活动的"素数因子(即那些平方不超过最低数的素数)包含至少一个单独的倍数。目前以移动筛子为代表。 SoE的另一个区别是，双端队列筛将实际因素存储在复合材料的槽中，而不是布尔值。
好。
该算法可根据需要扩展筛子窗口的大小，从而在较宽的范围内获得相当均匀的性能，直到筛子开始明显超过CPU的L1高速缓存的容量为止。完全适合的最后一个素数是25,237,523(第1,579,791个素数)，对于该算法的合理操作范围，它给出了一个大致的数字。
好。
该算法相当简单且健壮，并且与未分段的Eratosthenes筛相比，它甚至具有更大的性能。后者要快得多，只要它的筛子完全适合高速缓存即可，即对于带字节大小布尔值的仅赔率筛子而言，高达2 ^ 16。然后它的性能越来越下降，尽管尽管有障碍(至少在C / C ++，Pascal或Java / C＃这样的编译语言中)，但它始终始终比双端队列快得多。
好。
这是C＃中的双端队列筛选算法的渲染，因为尽管存在很多缺陷，但我发现该语言比原型非常繁琐而繁琐的C ++更适合用于原型算法和实验。 (旁注：我使用的是免费的LINQPad，它可以直接进入，而无需设置项目，makefile，目录或其他杂乱的杂物，并且它给我的交互性与python提示符相同)。
好。
C＃没有显式的双端队列类型，但是普通的List足以很好地演示算法。
好。
注意：此版本不使用双端队列作为质数，因为从n个质数中弹出sqrt(n)根本没有意义。除去100个素数并留下9900个有什么好处？至少以这种方式，所有素数都收集在一个整齐的向量中，以备进一步处理。
好。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| static List<int> deque_sieve (int n = 10000)
{
Trace.Assert(n >= 3);
var primes = new List<int>() { 2, 3 };
var sieve = new List<int>() { 0, 0, 0 };
for (int sieve_base = 5, current_prime_index = 1, current_prime_squared = 9; ; )
{
int base_factor = sieve[0];
if (base_factor != 0)
{
// the sieve base has a non-trivial factor - put that factor back into circulation
mark_next_unmarked_multiple(sieve, base_factor);
}
else if (sieve_base < current_prime_squared) // no non-trivial factor -> found a non-composite
{
primes.Add(sieve_base);
if (primes.Count == n)
return primes;
}
else // sieve_base == current_prime_squared
{
// bring the current prime into circulation by injecting it into the sieve ...
mark_next_unmarked_multiple(sieve, primes[current_prime_index]);
// ... and elect a new current prime
current_prime_squared = square(primes[++current_prime_index]);
}
// slide the sieve one step forward
sieve.RemoveAt(0); sieve_base += 2;
}
} |
这是两个帮助函数：
好。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| static void mark_next_unmarked_multiple (List<int> sieve, int prime)
{
int i = prime, e = sieve.Count;
while (i < e && sieve[i] != 0)
i += prime;
for ( ; e <= i; ++e) // no List<>.Resize()...
sieve.Add(0);
sieve[i] = prime;
}
static int square (int n)
{
return n * n;
} |
理解该算法的最简单方法可能是将其想象为片段大小为1的特殊分割的Eratosthenes筛网，并带有一个溢出区域，当素数射到该段的末端时，素数就会停止。到该段时，该段的单个单元格(也称为sieve[0])已经过筛，因为它是溢出区的一部分而被溢出。
好。
用sieve[0]表示的数字保留在sieve_base中，尽管sieve_front或window_base也是一个好名字，可以与Ben的代码或分段/窗口式筛子的实现方式相似。
好。
如果sieve[0]包含非零值，则该值是sieve_base的因数，因此可以将其识别为复合值。由于单元格0是该因子的倍数，因此很容易计算其下一跳，也就是0加该因子。如果该单元格已被另一个因子占据，那么我们只需再次添加该因子，依此类推，直到找到当前没有其他因子停放的该因子的倍数(如果需要，可以扩展筛子)。这也意味着，不需要像普通分段筛那样存储从一个分段到另一个分段的各种质数的当前工作偏移。每当我们在sieve[0]中找到一个因数时，其当前工作偏移量为0。
好。
当前的质数通过以下方式发挥作用。质数只能在其自身在流中出现后才成为电流(即，由于未标记为素而被检测为质数时)，它将一直保持电流，直到sieve[0]到达其平方的确切时刻为止。就像在普通的SoE中一样，由于较小的素数的活动，必须删除了该素数的所有较低倍数。但是，所有较小的素数都不能脱离平方，因为平方的唯一因素是素数本身，并且此时尚未流通。这就解释了算法在sieve_base == current_prime_squared情况下采取的动作(顺便说一下，这意味着sieve[0] == 0)。
好。
现在，很容易解释情况sieve[0] == 0 && sieve_base < current_prime_squared：这意味着sieve_base不能是小于当前质数的任何质数的倍数，否则它将被标记为复合。我也不可以是当前素数的较高倍数，因为它的值小于当前素数的平方。因此，它必须是一个新的素数。
好。
该算法显然受Eratosthenes筛的启发，但同样明显的是，它有很大的不同。 Eratosthenes筛网的基本操作简单，从而获得了卓越的速度：长时间的操作仅需一个索引添加和一个存储即可。
好。
这是Eratosthenes的一个简单，无节段的筛子，我通常使用它来筛分ushort范围(即最高达2 ^ 16)的素数素数。对于这篇文章，我通过将int替换为ushort，将其修改为可工作于2 ^ 16以上。
好。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| static List<int> small_odd_primes_up_to (int n)
{
var result = new List<int>();
if (n < 3)
return result;
int sqrt_n_halved = (int)(Math.Sqrt(n) - 1) >> 1, max_bit = (n - 1) >> 1;
var odd_composite = new bool[max_bit + 1];
for (int i = 3 >> 1; i <= sqrt_n_halved; ++i)
if (!odd_composite[i])
for (int p = (i << 1) + 1, j = p * p >> 1; j <= max_bit; j += p)
odd_composite[j] = true;
result.Add(3); // needs to be handled separately because of the mod 3 wheel
// read out the sieved primes
for (int i = 5 >> 1, d = 1; i <= max_bit; i += d, d ^= 3)
if (!odd_composite[i])
result.Add((i << 1) + 1);
return result;
} |
当筛选前10000个素数时，将超过典型的32 KiByte的L1高速缓存，但是该功能仍然非常快(即使在C＃中也为毫秒级)。
好。
如果将此代码与双端队列筛选器进行比较，则很容易看到双端队列筛子的操作要复杂得多，并且由于它总是连续进行尽可能短的交叉，因此它无法有效地摊销其开销。 (在跳过所有已被舍弃的倍数之后，恰好是一个单一的舍弃)。
好。
注意：C＃代码使用int而不是uint，因为较新的编译器习惯为uint生成次标准代码，可能是为了将人们推向有符号整数...在上述代码的C ++版本中，我整个自然使用unsigned；基准必须使用C ++，因为我希望它基于假定足够的双端队列类型(std::deque；使用unsigned short不会带来性能提升)。以下是我的Haswell笔记本电脑(VC ++ 2015 / x64)的编号：
好。
1
2
3
| deque vs simple: 1.802 ms vs 0.182 ms
deque vs simple: 1.836 ms vs 0.170 ms
deque vs simple: 1.729 ms vs 0.173 ms |
注意：C＃时间几乎是C ++计时的两倍，这对C＃来说是相当不错的，并且ìt显示List即使被当成双端队列也没有懈怠。
好。
即使它已经运行超出其正常工作范围(L1高速缓存大小超出50％，伴随的高速缓存抖动)，简单的筛分代码仍然可以将双端队列从水中吹走。此处的主要部分是对筛分质数的读取，这不受缓存问题的影响很大。在任何情况下，该函数都设计用于筛分因素因子，即3级筛分层次中的0级，通常，它仅返回几百个因子或几千个因子。因此其简单性。
好。
通过使用分段筛并优化用于提取筛分质数的代码(步进的mod 3展开两次，或mod 15展开一次)，可以将性能提高一个数量级以上，但是可以从中挤出更多性能通过使用带有所有修整的mod 16或mod 30车轮(即，所有残渣完全展开)来编码。我对"代码审阅"中的查找素数定位质数的回答中对此进行了解释，其中讨论了类似的问题。但是很难看出将一次性任务的时间提高到毫秒以下的意义...
好。
让我们稍微看一下，下面是筛选多达100,000,000个C ++的时间：
好。
1
2
3
| deque vs simple: 1895.521 ms vs 432.763 ms
deque vs simple: 1847.594 ms vs 429.766 ms
deque vs simple: 1859.462 ms vs 430.625 ms |
相比之下，在C＃中带有一些铃铛和口哨声的分段筛网在95 ms内完成了相同的工作(没有C ++计时，因为我目前仅在C＃中进行挑战代码)。
好。
在像Python这样的解释型语言中，情况看起来可能完全不同，在每种语言中，每项操作的成本都很高，而解释器的开销使由于预测的分支或预测错误的分支或子周期操作(移位，加法)与多周期操作(乘法)导致的所有差异相形见war。 ，甚至除法)。这势必削弱Eratosthenes筛的简单性优势，这可能会使双端队列解决方案更具吸引力。
好。
同样，其他答复者在本主题中报告的许多时间安排可能都以输出时间为主。 那是一场完全不同的战争，我的主要武器是一个像这样的简单班级：
好。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
| class CCWriter
{
const int SPACE_RESERVE = 11; // UInt31 + '
'
public static System.IO.Stream BaseStream;
static byte[] m_buffer = new byte[1 << 16]; // need 55k..60k for a maximum-size range
static int m_write_pos = 0;
public static long BytesWritten = 0; // for statistics
internal static ushort[] m_double_digit_lookup = create_double_digit_lookup();
internal static ushort[] create_double_digit_lookup ()
{
var lookup = new ushort[100];
for (int lo = 0; lo < 10; ++lo)
for (int hi = 0; hi < 10; ++hi)
lookup[hi * 10 + lo] = (ushort)(0x3030 + (hi << 8) + lo);
return lookup;
}
public static void Flush ()
{
if (BaseStream != null && m_write_pos > 0)
BaseStream.Write(m_buffer, 0, m_write_pos);
BytesWritten += m_write_pos;
m_write_pos = 0;
}
public static void WriteLine ()
{
if (m_buffer.Length - m_write_pos < 1)
Flush();
m_buffer[m_write_pos++] = (byte)'
';
}
public static void WriteLinesSorted (int[] values, int count)
{
int digits = 1, max_value = 9;
for (int i = 0; i < count; ++i)
{
int x = values[i];
if (m_buffer.Length - m_write_pos < SPACE_RESERVE)
Flush();
while (x > max_value)
if (++digits < 10)
max_value = max_value * 10 + 9;
else
max_value = int.MaxValue;
int n = x, p = m_write_pos + digits, e = p + 1;
m_buffer[p] = (byte)'
';
while (n >= 10)
{
int q = n / 100, w = m_double_digit_lookup[n - q * 100];
n = q;
m_buffer[--p] = (byte)w;
m_buffer[--p] = (byte)(w >> 8);
}
if (n != 0 || x == 0)
m_buffer[--p] = (byte)((byte)'0' + n);
m_write_pos = e;
}
}
} |
写10000个(排序的)数字所需的时间少于1毫秒。 这是一个静态类，因为它旨在以文本形式包含在编码挑战提交中，从而避免了大惊小怪且零开销。
好。
总的来说，我发现如果对全部批次进行集中工作会更快得多，这意味着筛选出一定范围，然后将所有质数提取到向量/阵列中，然后展开整个阵列，再筛选下一个范围，依此类推， 而不是将所有事物混合在一起。 将单独的功能集中于特定任务也可以使混合和匹配更加容易，可以重用，并且可以简化开发/测试。
好。
好。
根据GateKiller的改编和后续内容，这是我使用的最终版本。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| 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这样的解决方案更快。
这是我的VB 2008代码，它在我的工作笔记本电脑上1分钟27秒内发现所有小于10,000,000的素数。它跳过偶数，仅查找小于测试数平方根的素数。它仅用于查找从0到指定值的素数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles
Button1.Click
Dim TestNum As Integer
Dim X As Integer
Dim Z As Integer
Dim TM As Single
Dim TS As Single
Dim TMS As Single
Dim UnPrime As Boolean
Dim Sentinal As Integer
Button1.Text ="Thinking"
Button1.Refresh()
Sentinal = Val(SentinalTxt.Text)
UnPrime = True
Primes(0) = 2
Primes(1) = 3
Z = 1
TM = TimeOfDay.Minute
TS = TimeOfDay.Second
TMS = TimeOfDay.Millisecond
For TestNum = 5 To Sentinal Step 2
Do While Primes(X) <> 0 And UnPrime And Primes(X) ^ 2 <= TestNum
If Int(TestNum / Primes(X)) - (TestNum / Primes(X)) = 0 Then
UnPrime = False
End If
X = X + 1
Loop
If UnPrime = True Then
X = X + 1
Z = Z + 1
Primes(Z) = TestNum
End If
UnPrime = True
X = 0
Next
Button1.Text ="Finished with" & Z
TM = TimeOfDay.Minute - TM
TS = TimeOfDay.Second - TS
TMS = TimeOfDay.Millisecond - TMS
ShowTime.Text = TM &":" & TS &":" & TMS
End Sub |
以下Mathcad代码在3分钟内计算了前一百万个素数。
请记住，这将对所有数字使用浮点双精度，并且基本上是解释性的。我希望语法清楚。
这是使用SoE形式的C ++解决方案：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include <iostream>
#include <deque>
typedef std::deque<int> mydeque;
void my_insert( mydeque & factors, int factor ) {
int where = factor, count = factors.size();
while( where < count && factors[where] ) where += factor;
if( where >= count ) factors.resize( where + 1 );
factors[ where ] = factor;
}
int main() {
mydeque primes;
mydeque factors;
int a_prime = 3, a_square_prime = 9, maybe_prime = 3;
int cnt = 2;
factors.resize(3);
std::cout <<"2 3";
while( cnt < 10000 ) {
int factor = factors.front();
maybe_prime += 2;
if( factor ) {
my_insert( factors, factor );
} else if( maybe_prime < a_square_prime ) {
std::cout << maybe_prime <<"";
primes.push_back( maybe_prime );
++cnt;
} else {
my_insert( factors, a_prime );
a_prime = primes.front();
primes.pop_front();
a_square_prime = a_prime * a_prime;
}
factors.pop_front();
}
std::cout << std::endl;
return 0;
} |
请注意，此版本的Sieve可以无限期地计算素数。
还要注意，STL deque需要花费O(1)时间来执行push_back，pop_front和通过下标进行随机访问。
resize操作花费O(n)时间，其中<??x6>是要添加的元素数。由于我们如何使用此函数，我们可以将其视为一个小常数。
my_insert中的while循环的主体执行了O(log log n)次，其中n等于变量maybe_prime。这是因为对于maybe_prime的每个素数因子，while的条件表达式将一次为true。请参阅Wikipedia上的"除数函数"。
乘以调用my_insert的次数，表明列出n素数需要花费O(n log log n)时间...毫无疑问，这是Eratosthenes筛子应该具有的时间复杂性。
但是，尽管此代码是有效的，但它并不是最有效的……我强烈建议使用专门的库来生成素数，例如primesieve。任何真正高效，经过优化的解决方案，所花费的代码将超过任何人想要键入Stackoverflow的代码。
与"已知范围的"素数算法相比，使用Eratosthenes的Sieve可以更快地进行计算。
通过使用其Wiki(https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)中的伪代码，我可以在C＃上获得解决方案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| /// Get non-negative prime numbers until n using Sieve of Eratosthenes.
public int[] GetPrimes(int n) {
if (n <= 1) {
return new int[] { };
}
var mark = new bool[n];
for(var i = 2; i < n; i++) {
mark[i] = true;
}
for (var i = 2; i < Math.Sqrt(n); i++) {
if (mark[i]) {
for (var j = (i * i); j < n; j += i) {
mark[j] = false;
}
}
}
var primes = new List<int>();
for(var i = 3; i < n; i++) {
if (mark[i]) {
primes.Add(i);
}
}
return primes.ToArray();
} |
GetPrimes(100000000)花费2s和330ms。
注意：值可能会有所不同，具体取决于硬件规格。
由于您只需要前10000个素数，因此我建议不要编码复杂的算法
下列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| boolean isPrime(int n){
//even but is prime
if(n==2)
return true;
//even numbers filtered already
if(n==0 || n==1 || n%2==0)
return false;
// loop for checking only odd factors
// i*i <= n (same as i<=sqrt(n), avoiding floating point calculations)
for(int i=3 ; i*i <=n ; i+=2){
// if any odd factor divides n then its not a prime!
if(n%i==0)
return false;
}
// its prime now
return true;
} |
现在通话是您需要的主要通话
1
2
3
4
5
| for(int i=1 ; i<=1000 ; i++){
if(isPrime(i)){
//do something
}
} |
我花了一些时间编写一个计算大量素数的程序，这是我用来计算包含前1.000.000.000个素数的文本文件的代码。它是德语，但是有趣的部分是方法calcPrimes()。素数存储在称为Primzahlen的数组中。我建议使用64位CPU，因为计算使用64位整数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
| import java.io.*;
class Primzahlengenerator {
long[] Primzahlen;
int LastUnknown = 2;
public static void main(String[] args) {
Primzahlengenerator Generator = new Primzahlengenerator();
switch(args.length) {
case 0: //Wenn keine Argumente übergeben worden:
Generator.printHelp(); //Hilfe ausgeben
return; //Durchfallen verhindern
case 1:
try {
Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];
}
catch (NumberFormatException e) {
System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. "Tausend", sondern in Ziffern z.B. "1000" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben
Generator.printHelp(); //Generelle Hilfe ausgeben
return;
}
break;//dutchfallen verhindern
case 2:
switch (args[1]) {
case"-l":
System.out.println("Sie müsen auch eine Datei angeben!"); //Hilfemitteilung ausgeben
Generator.printHelp(); //Generelle Hilfe ausgeben
return;
}
break;//durchfallen verhindern
case 3:
try {
Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];
}
catch (NumberFormatException e) {
System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. "Tausend", sondern in Ziffern z.B. "1000" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben
Generator.printHelp(); //Generelle Hilfe ausgeben
return;
}
switch(args[1]) {
case"-l":
Generator.loadFromFile(args[2]);//Datei Namens des Inhalts von Argument 3 lesen, falls Argument 2 ="-l" ist
break;
default:
Generator.printHelp();
break;
}
break;
default:
Generator.printHelp();
return;
}
Generator.calcPrims();
}
void printHelp() {
System.out.println("Sie müssen als erstes Argument angeben, die wieviel ersten Primzahlen sie berechnen wollen."); //Anleitung wie man das Programm mit Argumenten füttern muss
System.out.println("Als zweites Argument k?nnen sie "-l" w?hlen, worauf die Datei, aus der die Primzahlen geladen werden sollen,");
System.out.println("folgen muss. Sie muss genauso aufgebaut sein, wie eine Datei Primzahlen.txt, die durch den Aufruf "java Primzahlengenerator 1000 > Primzahlen.txt" entsteht.");
}
void loadFromFile(String File) {
// System.out.println("Lese Datei namens: "" + File +""");
try{
int x = 0;
BufferedReader in = new BufferedReader(new FileReader(File));
String line;
while((line = in.readLine()) != null) {
Primzahlen[x] = new Long(line).longValue();
x++;
}
LastUnknown = x;
} catch(FileNotFoundException ex) {
System.out.println("Die angegebene Datei existiert nicht. Bitte geben sie eine existierende Datei an.");
} catch(IOException ex) {
System.err.println(ex);
} catch(ArrayIndexOutOfBoundsException ex) {
System.out.println("Die Datei enth?lt mehr Primzahlen als der reservierte Speicherbereich aufnehmen kann. Bitte geben sie als erstes Argument eine gr??ere Zahl an,");
System.out.println("damit alle in der Datei enthaltenen Primzahlen aufgenommen werden k?nnen.");
}
/* for(long prim : Primzahlen) {
System.out.println("" + prim);
} */
//Hier soll code stehen, der von der Datei mit angegebenem Namen ( Wie diese aussieht einfach durch angeben von folgendem in cmd rausfinden:
//java Primzahlengenerator 1000 > 1000Primzahlen.txt
//da kommt ne textdatei, die die primzahlen enth?lt. mit Long.decode(String ziffern).longValue();
//erh?lt man das was an der entsprechenden stelle in das array soll. die erste zeile soll in [0] , die zweite zeile in [1] und so weiter.
//falls im arry der platz aus geht(die exception kenn ich grad nich, aber mach mal:
//int[] foo = { 1, 2, 3};
//int bar = foo[4];
//dann kriegst ne exception, das ist die gleiche die man kriegt, wenn im arry der platzt aus geht.
}
void calcPrims() {
int PrimzahlNummer = LastUnknown;
// System.out.println("LAstUnknown ist:" + LastUnknown);
Primzahlen[0] = 2;
Primzahlen[1] = 3;
long AktuelleZahl = Primzahlen[PrimzahlNummer - 1];
boolean IstPrimzahl;
// System.out.println("2");
// System.out.println("3");
int Limit = Primzahlen.length;
while(PrimzahlNummer < Limit) {
IstPrimzahl = true;
double WurzelDerAktuellenZahl = java.lang.Math.sqrt(AktuelleZahl);
for(int i = 1;i < PrimzahlNummer;i++) {
if(AktuelleZahl % Primzahlen[i] == 0) {
IstPrimzahl = false;
break;
}
if(Primzahlen[i] > WurzelDerAktuellenZahl) break;
}
if(IstPrimzahl) {
Primzahlen[PrimzahlNummer] = AktuelleZahl;
PrimzahlNummer++;
// System.out.println("" + AktuelleZahl);
}
AktuelleZahl = AktuelleZahl + 2;
}
for(long prim : Primzahlen) {
System.out.println("" + prim);
}
}
} |
我从事寻找素数的工作大约一年了。我发现这是最快的：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
| import static java.lang.Math.sqrt;
import java.io.PrintWriter;
import java.io.File;
public class finder {
public static void main(String[] args) {
primelist primes = new primelist();
primes.insert(3);
primes.insert(5);
File file = new File("C:/Users/Richard/Desktop/directory/file0024.txt");
file.getParentFile().mkdirs();
long time = System.nanoTime();
try{
PrintWriter printWriter = new PrintWriter ("file0024.txt");
int linenum = 0;
printWriter.print("2");
printWriter.print (" ,");
printWriter.print("3");
printWriter.print (" ,");
int up;
int down;
for(int i =1; i<357913941;i++){//
if(linenum%10000==0){
printWriter.println ("");
linenum++;
}
down = i*6-1;
if(primes.check(down)){
primes.insert(down);
//System.out.println(i*6-1);
printWriter.print ( down );
printWriter.print (" ,");
linenum++;
}
up = i*6+1;
if(primes.check(up)){
primes.insert(up);
//System.out.println(i*6+1);
printWriter.print ( up );
printWriter.print (" ,");
linenum++;
}
}
printWriter.println ("Time to execute");
printWriter.println (System.nanoTime()-time);
//System.out.println(primes.length);
printWriter.close ();
}catch(Exception e){}
}
}
class node{
node next;
int x;
public node (){
node next;
x = 3;
}
public node(int z) {
node next;
x = z;
}
}
class primelist{
node first;
int length =0;
node current;
public void insert(int x){
node y = new node(x);
if(current == null){
current = y;
first = y;
}else{
current.next = y;
current = y;
}
length++;
}
public boolean check(int x){
int p = (int)sqrt(x);
node y = first;
for(int i = 0;i<length;i++){
if(y.x>p){
return true;
}else if(x%y.x ==0){
return false;
}
y = y.next;
}
return true;
}
} |
1902465190909纳秒，从2开始达到2147483629。
这是我的代码
我的笔记本电脑在0.049655秒内获得前10,000个灌注，在6秒内获得前1,000,000个灌注，在15秒内获得前2,000,000
一点解释。该方法使用2种技术来查找素数
首先，任何非素数都是素数的倍数的组合，因此此代码通过将测试数除以较小的素数(而不是任何数字)来进行测试，这对于4位数字至少减少了10次计算，而对于更大的数目
其次，除了除以质数外，它仅除以小于或等于被测数根的质数，从而进一步减少了计算量，这是有效的，因为任何大于该数根的数都会有一个对应的数必须小于数字的根，但由于我们已经测试了所有小于该数字的根的数字，因此，我们不必为大于被测试的数字的根的数字打扰。
前10,000个素数的样本输出
https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0 https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk
这是C语言的代码，
输入1，然后输入10,000以打印出前10,000个素数。
编辑：我忘了它包含数学库，如果您在Windows或Visual Studio上，那应该没问题，但是在Linux上，您必须使用-lm参数编译代码，否则代码可能无法正常工作
示例：gcc -Wall -o"％e""％f" -lm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
| #include <stdio.h>
#include <math.h>
#include <time.h>
#include <limits.h>
/* Finding prime numbers */
int main()
{
//pre-phase
char d,w;
int l,o;
printf(" 1. Find first n number of prime numbers or Find all prime numbers smaller than n ?
"); // this question helps in setting the limits on m or n value i.e l or o
printf(" Enter 1 or 2 to get anwser of first or second question
");
// decision making
do
{
printf(" -->");
scanf("%c",&d);
while ((w=getchar()) != '
' && w != EOF);
if ( d == '1')
{
printf("
2. Enter the target no. of primes you will like to find from 3 to 2,000,000 range
-->");
scanf("%10d",&l);
o=INT_MAX;
printf(" Here we go!
");
break;
}
else if ( d == '2' )
{
printf("
2.Enter the limit under which to find prime numbers from 5 to 2,000,000 range
-->");
scanf("%10d",&o);
l=o/log(o)*1.25;
printf(" Here we go!
");
break;
}
else printf("
Try again
");
}while ( d != '1' || d != '2' );
clock_t start, end;
double cpu_time_used;
start = clock(); /* starting the clock for time keeping */
// main program starts here
int i,j,c,m,n; /* i ,j , c and m are all prime array 'p' variables and n is the number that is being tested */
int s,x;
int p[ l ]; /* p is the array for storing prime numbers and l sets the array size, l was initialized in pre-phase */
p[1]=2;
p[2]=3;
p[3]=5;
printf("%10dst:%10d
%10dnd:%10d
%10drd:%10d
",1,p[1],2,p[2],3,p[3]); // first three prime are set
for ( i=4;i<=l;++i ) /* this loop sets all the prime numbers greater than 5 in the p array to 0 */
p[i]=0;
n=6; /* prime number testing begins with number 6 but this can lowered if you wish but you must remember to update other variables too */
s=sqrt(n); /* 's' does two things it stores the root value so that program does not have to calaculate it again and again and also it stores it in integer form instead of float*/
x=2; /* 'x' is the biggest prime number that is smaller or equal to root of the number 'n' being tested */
/* j ,x and c are related in this way, p[j] <= prime number x <= p[c] */
// the main loop begins here
for ( m=4,j=1,c=2; m<=l && n <= o;)
/* this condition checks if all the first 'l' numbers of primes are found or n does not exceed the set limit o */
{
// this will divide n by prime number in p[j] and tries to rule out non-primes
if ( n%p[j]==0 )
{
/* these steps execute if the number n is found to be non-prime */
++n; /* this increases n by 1 and therefore sets the next number 'n' to be tested */
s=sqrt(n); /* this calaulates and stores in 's' the new root of number 'n' */
if ( p[c] <= s && p[c] != x ) /* 'The Magic Setting' tests the next prime number candidate p[c] and if passed it updates the prime number x */
{
x=p[c];
++c;
}
j=1;
/* these steps sets the next number n to be tested and finds the next prime number x if possible for the new number 'n' and also resets j to 1 for the new cycle */
continue; /* and this restarts the loop for the new cycle */
}
// confirmation test for the prime number candidate n
else if ( n%p[j]!=0 && p[j]==x )
{
/* these steps execute if the number is found to be prime */
p[m]=n;
printf("%10dth:%10d
",m,p[m]);
++n;
s = sqrt(n);
++m;
j=1;
/* these steps stores and prints the new prime number and moves the 'm' counter up and also sets the next number n to be tested and also resets j to 1 for the new cycle */
continue; /* and this restarts the loop */
/* the next number which will be a even and non-prime will trigger the magic setting in the next cycle and therfore we do not have to add another magic setting here*/
}
++j; /* increases p[j] to next prime number in the array for the next cycle testing of the number 'n' */
// if the cycle reaches this point that means the number 'n' was neither divisible by p[j] nor was it a prime number
// and therfore it will test the same number 'n' again in the next cycle with a bigger prime number
}
// the loops ends
printf(" All done !!
");
end = clock();
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
printf(" Time taken : %lf sec
",cpu_time_used);
} |
这是我制作的代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| enter code here
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include
using namespace std;
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT*/
unsigned long int n;
int prime(unsigned long int);
scanf("%ld",&n);
unsigned long int val;
for(unsigned long int i=0;i<n;i++)
{
int flag=0;
scanf("%ld",&val);
flag=prime(val);
if(flag==1)
printf("yes
");
else
printf("no
");
}
return 0;
}
int prime(unsigned long int n)
{
if(n==2) return 1;
else if (n == 1||n%2==0) return 0;
for (unsigned long int i=3; i<=sqrt(n); i+=2)
if (n%i == 0)
return 0;
return 1;
} |
在Javascript中使用Array.prototype.find()方法。 2214.486毫秒
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| function isPrime (number) {
function prime(element) {
let start = 2;
while (start <= Math.sqrt(element)) {
if (element % start++ < 1) {
return false;
}
}
return element > 1;
}
return [number].find(prime)
}
function logPrimes (n) {
let count = 0
let nth = n
let i = 0
while (count < nth) {
if (isPrime(i)) {
count++
console.log('i', i) //NOTE: If this line is ommited time to find 10,000th prime is 121.157ms
if (count === nth) {
console.log('while i', i)
console.log('count', count)
}
}
i++
}
}
console.time(logPrimes)
logPrimes(10000)
console.timeEnd(logPrimes) // 2214.486ms |
我可以给您一些提示，您必须实施它。
对于每个数字，获取该数字的一半。例如。对于检查21，仅将其除以2-10即可得到余数。
如果它是奇数，则只能除以奇数，反之亦然。如为21，则仅除以3、5、7、9。
到目前为止，我掌握的最有效的方法。
我刚开始学习它时就使用python编写了它，并且效果很好。此代码生成的第10,000个素数与http://primes.utm.edu/lists/small/10000.txt中提到的相同。要检查n是否为质数，请用n除以2至sqrt(n)之间的数字。如果此数字范围中的任何一个完美地除以n，则它不是素数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| 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)) |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| using System;
namespace ConsoleApplication2
{
class Program
{
static void Main(string[] args)
{
int n, i = 3, j, c;
Console.WriteLine("Please enter your integer:");
n = Convert.ToInt32(Console.ReadLine());
if (n >= 1)
{
Console.WriteLine("First" + n +" Prime Numbers are");
Console.WriteLine("2");
}
for(j=2;j<=n;)
{
for(c=2;c<=i-1;c++)
{
if(i%c==0)
break;
}
if(c==i)
{
Console.WriteLine(i);
j++;
}
i++;
}
Console.Read();
}
}
} |
