最初的10000个素数的最有效的代码？
我想打印第一个10000个素数。 任何人都可以给我这个最有效的代码？ 澄清：
- 如果您的代码在n> 10000时效率低下，那并不重要。
- 代码的大小并不重要。
- 你不能以任何方式硬编码值。
Atkin的Sieve可能是你正在寻找的，它的上限运行时间是O（N / log log N）。
如果只运行数字1和多于6的倍数，则可能会更快，因为所有3以上的素数都是6的倍数之一。 我的声明的资源
我推荐一个筛子，不是埃拉托斯汀的筛子，就是阿特金的筛子。
筛或Eratosthenes可能是find素数列表最直观的方法。 基本上你：
- 写下从2到任意数量的数字列表，比如说1000。
- 取第一个没有交叉的数字（第一次迭代为2），并从列表中除去该数字的所有倍数。
- 重复第2步，直到到达列表的末尾。 所有未被截断的数字都是素数。
显然有很多优化可以使这个algorithm的工作更快，但这是基本的想法。
Atkin的筛选使用了类似的方法，但不幸的是，我不太了解它向你解释。 但是我知道我连接的algorithm需要8秒钟的时间才能找出古老的奔腾II-350上的所有质数高达10亿
源码： http ://web.archive.org/web/20140705111241/http: //primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/
Atkin源代码： http : //cr.yp.to/primegen.html
这不是严格的硬编码限制，而是非常接近。 为什么不以编程方式下载此列表并打印出来呢？
GateKiller ， if在foreach循环中添加一个break ，怎么样？ 这会加快事情很多，因为如果像6可以被2整除，你不需要检查3和5.（如果我有足够的声望，我会投票你的解决scheme:-) …）
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 + " "); } }
@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）位的内存（AOL Atkin，DJBernstein，2004）的Eratosthenes筛略好一些。 这些渐近计算的复杂性包括简单的优化，如轮子分解，并将计算分割成更小的块。
给定沿着O(N) （对于Eratosthenes）和O(N/log(log(N))) （对于Atkin）的渐近计算复杂性，我们不能说（对于小的N=10_000 ）如果实施将会更快。
Achim Flammenkamp在“Eratosthenes的筛”中写道：
被引用：
@ NUM1
对于大于10 ^ 9的区间，对于那些> 10 ^ 10的区间来说，Eratosthenes的筛子比使用不可简化的二元二次forms的Atkins和Bernstein的筛子更好。 W.Galway博士的论文第5段提供了背景资料。 论文。
因此对于10_000筛子的10_000可以10_000筛子更快。
回答OP的代码是prime_sieve.c （由num1引用）
在Haskell中，我们几乎可以一字不差地写下Eratosthenes筛的math定义，“ 素数是大于1的自然数，没有任何复合数，通过枚举每个素数的倍数来find复合数 ：”
primes = 2 : minus [3..] (foldr (\p r-> p*p : union [p*p+p, p*p+2*p..] r) [] primes)
primes !! 10000 primes !! 10000几乎是瞬间的。
参考文献：
- Eratosthenes的筛子
- 理查德·伯德的筛子（见第10,11页）
- 减号，联合
上面的代码很容易被调整为仅对赔率进行操作， primes = 2:3:minus [5,7..] (foldr (\pr -> 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 ks@(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 (gy)) x = f (gx) ）。
使用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针对这种事情进行了高度优化。 除非你真的想通过编写自己的algorithm来理解algorithm，否则你会被build议在C中使用libGMP。
我已经调整了CodeProject上的代码来创build以下内容：
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服务器上进行testing，花了大约1分钟的时间运行。
根本没有效率，但是可以使用正则expression式来testing素数。
/^1?$|^(11+?)\1+$/
这testing对于由k “ 1 ”组成的stringk是否不是素数 （即，string是由一个“ 1 ”还是可以表示为n元产品的任何数目的“ 1 ”组成）。
这是几天前我在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 }
因为简单和速度，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时间find素数（在奔腾双核E2140 1.6 GHz，使用单核）
lim = 100,000,000〜4s
从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”的build议，并改变了一些变数，使其更适合我。 （我在欧拉工作，需要第10001个素数）
筛子似乎是错误的答案。 筛子为您提供最多 N的素数，而不是第一个N素数。 运行@Imran或@Andrew Szeto，你可以得到N的素数。
筛子可能仍然可用，如果您不断尝试筛选越来越多的数字，直到您达到一定的结果集大小，并使用一些caching已获得的数字，但我相信它仍然不会比像@ Pat的解决scheme。
在Python中
import gmpy p=1 for i in range(10000): p=gmpy.next_prime(p) print p
BenGoldberg提到的deque筛分algorithm值得仔细观察，不仅因为它非常优雅，而且因为偶尔在实践中有用（不像Atkin的Sieve，这纯粹是一个学术性的练习）。
deque sievealgorithm背后的基本思想是使用一个小的滑动筛子，这个筛子的大小足以包含至less一个单独的倍数，用于每个当前“活动”的素数因子 – 也就是那些平方不超过最小数量的素数目前由移动的筛子代表。 SoE的另一个区别是，deque筛将实际因素存储在复合材料的槽中，而不是布尔值。
该algorithm根据需要扩展筛窗的大小，从而在广泛的范围内实现相当均匀的性能，直到筛网开始明显超过CPU L1caching的容量。 最后一个完全适合的素数是25237523（1,579,791素数），这为algorithm的合理操作范围提供了一个粗略的数字。
该algorithm相当简单和强大，甚至比不分割的Eratosthenes筛的性能更广泛。 后者是很快，只要它的筛子完全适合caching，即高达2 ^ 16的字符大小bools的赔率筛选。 然后它的性能下降越来越多，尽pipe尽pipe有障碍（至less在C / C ++，Pascal或Java / C＃等编译语言中），它始终比deque快得多。
下面是C＃中的deque sievealgorithm的一个渲染，因为我发现这个语言 – 尽pipe有许多缺陷 – 比原型繁琐和迂腐的C ++更适用于原型algorithm和实验。 （旁注：我正在使用免费的LINQPad ，这使得可以毫不费力地设置项目，makefile，目录或者其他任何东西，并且它提供了与python提示符相同程度的交互性）。
C＃没有明确的dequetypes，但是普通的List<int>对于演示algorithm来说足够好。
注意：这个版本并没有使用一个双精度的素数，因为从n个素数中popupsqrt（n）是没有意义的。 除去100个素数和离开9900会有什么好处呢？ 至less这样，所有素数都被收集在一个整齐的向量中，准备好进一步处理。
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; } }
这是两个帮手function：
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; }
理解这个algorithm最简单的方法就是把它想象成一个分段大小为1的Eratosthenes的特殊的分段筛，伴随着一个溢出区域，在这个区域里，当这些素数在这个区段的末端射击的时候，它们会停下来。 除了这个段的单细胞（又名sieve[0] ）已经被筛选了，因为它是溢stream区的一部分。
由sieve[0]表示的数字保存在sieve_base ，尽pipesieve_front或window_base也可以是一个很好的名字，可以与Ben的代码或者分段/窗口化的筛子相提并论。
如果sieve[0]包含非零值，则该值是sieve_base的因子，因此可以将其识别为复合。 由于单元0是这个因子的倍数，所以很容易计算它的下一跳，这只是0加上那个因子。 如果这个单元格已经被另一个因素占用，那么我们再简单地加上这个因素，等等，直到find当前没有其他因素停泊的因子的倍数（如果需要的话，扩大筛子）。 这也意味着不需要像在普通的分段筛中一样将各个素数的当前工作偏移从一个区段存储到下一个区段。 每当我们在sieve[0]find一个因子，它的当前工作偏移就是0。
目前的素数以如下方式发挥作用。 一个素数只有在它自己在stream中出现之后才能变为stream动（即当它被检测为素数时，因为没有标记因子），并且它将保持当前直到sieve[0]达到其正方形的确切时刻。 由于素数较小的活动，所有这个素数的较低倍数都必须被删除，就像在一个正常的SoE中一样。 但是没有一个较小的素数可以离开这个正方形，因为这个正方形的唯一因素就是素数本身，在这个点上它还没有stream通。 这就解释了algorithm在sieve_base == current_prime_squared （ sieve_base == current_prime_squared ， sieve[0] == 0 ）的情况下所采取的行动。
现在sieve[0] == 0 && sieve_base < current_prime_squared很容易解释：这意味着sieve_base不能是任何小于当前素数的素数的倍数，否则将被标记为复合。 我不能是当前素数的更高倍数，因为它的值小于当前素数的平方。 因此它一定是一个新的素数。
该algorithm显然是由Eratosthenes的Sieve启发，但同样显然它是非常不同的。 Eratosthenes的筛子从其基本操作的简单性中获得了其优越的速度：对于操作的每一个步骤，单个索引添加和一个存储都是长时间的工作。
这是一个简单的，不分割的Eratosthenes筛，我通常用它来筛选素数在最高范围，即高达2 ^ 16。 对于这篇文章，我已经修改它超过2 ^ 16通过int替代ushort
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个素数时，将会超出32K字节的典型L1caching，但function仍然非常快（即使在C＃中也只有几分之一毫秒）。
如果你把这个代码和deque筛比较，很容易看出deque筛的操作要复杂得多，而且不能有效地分摊它的开销，因为它始终是尽可能短的延伸交叉点（在跳过已经被划掉的所有倍数之后，正好是一个单独的交叉）。
注意：C＃代码使用int而不是uint因为较新的编译器习惯为uint生成不合标准的代码，可能是为了将人推向有符号的整数…在上面的代码的C ++版本中，我自然地使用了unsigned整数; 基准必须在C ++中，因为我希望它基于一个所谓的足够的dequetypes（ std::deque<unsigned> ;使用unsigned short没有性能增益）。 下面是我的Haswell笔记本电脑（VC ++ 2015 / x64）的编号：
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＃来说是相当不错的，并且表明即使被滥用作为双端队列， List<int>也不是懒散的。
尽pipe已经在正常的工作范围之外（L1高速caching大小超过了50％，伴随着高速caching抖动），简单的筛码依然将水stream从水中吹出。 这里的主要部分是读取筛选出来的素数，而这并不受caching问题的影响。 在任何情况下，这个函数都是为筛选因素而devise的，即在一个3级筛选层级中的0级，通常它只能返回几百个因子或几千个因子。 因此它的简单性。
通过使用分段筛和优化提取筛选的素数的代码（阶梯式模型3和展开两次，或模型15并展开一次），性能可以提高超过一个数量级，并且更多的性能可以被挤出代码通过使用mod 16或mod 30的轮子与所有的修剪（即完全展开所有残留物）。 类似这样的事情在我回答“在Code Review上find黄金定位素数”的答案中已经有解释，在这里讨论了类似的问题。 但是一次性任务的亚毫秒级提升难度很大
为了看清楚一些事情，下面是筛选高达100,000,000的C ++定时：
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＃语言编写的分段式筛网在95ms内完成了相同的工作（没有C ++时序可用，因为我现在只用C＃编写挑战）。
在像Python这样的解释性语言中，事情可能看起来截然不同，在这种语言中，每个操作的代价都很高，解释器开销由于预测与错误预测分支或子周期操作（移位，加法）与多周期操作（乘法，甚至可能是分工）。 这必然会削弱Eratosthenes Sieve的简单优势，这可能会使deque解决scheme更具吸引力。
而且，其他受访者在这个话题中所报告的很多时间可能都以输出时间为主。 这是一场完全不同的战争，我的主要武器是这样一个简单的类：
class CCWriter { const int SPACE_RESERVE = 11; // UInt31 + '\n' 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)'\n'; } 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)'\n'; 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（sorting）号码的时间less于1毫秒。 这是一个静态类，因为它旨在将文本包含在编码挑战提交中，同时最小的麻烦和零开销。
一般来说，如果在整个批次上完成重点工作，意味着筛选一定范围，然后将所有素数提取到一个向量/数组，然后将整个数组爆炸出来，然后筛选下一个范围，以此类推，而不是把所有东西混合在一起。 具有专注于特定任务的单独function也使混合和匹配变得更加容易，使其能够重用，并且便于开发/testing。
这是我的VB 2008代码，在我的工作笔记本电脑上，在1分27秒内find所有素数<10,000,000。 它跳过偶数，只查找<testing编号sqrt的素数。 它只是devise用来find从0到最终价值的素数。
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分钟内计算了第一百万个素数。
请记住，这将是所有的数字使用浮点双打，基本上是解释。 我希望语法清晰。
这是一个C ++解决scheme，使用一种SoEforms：
#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和随机访问（尽pipe是下标）。
resize操作需要O(n)时间，其中n是要添加的元素的数量。 由于我们如何使用这个function，我们可以对待这个是一个小常量。
my_insert while循环的my_insert被执行O(log log n)次，其中n等于variablesmaybe_prime 。 这是因为对于maybe_prime每个主要因素， maybe_prime的条件expression式将被评估为true。 请参阅维基百科上的“ 除数函数 ”。
乘以my_insert被调用的次数，表明它应该用O(n log log n)时间来列出n素数……这不意外的是，Eratosthenes的筛子应该具有的时间复杂度。
然而，虽然这个代码是有效的，但它不是最有效的 …我强烈build议使用专门的素材库，如primesieve 。 任何真正高效的，优化的解决scheme，将比任何人想要input到Stackoverflow需要更多的代码。
使用Eratosthenes的筛子，与“已知的”素数algorithm相比，计算速度相当快。
通过使用wiki中的伪代码（ https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ），我可以在C＃上获得解决scheme。
/// 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) takes 2s and 330ms.
NOTE : Value might vary depend on Hardware Specifications.
I spend some time writing a program calculating a lot of primes and this is the code I'm used to calculate a text file containing the first 1.000.000.000 primes. It's in German, but the interesting part is the method calcPrimes() . The primes are stored in an array called Primzahlen. I recommend a 64bit CPU because the calculations are with 64bit integers.
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 zB \"Tausend\", sondern in Ziffern zB \"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 zB \"Tausend\", sondern in Ziffern zB \"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); } } }
I have written this using python, as I just started learning it, and it works perfectly fine. The 10,000th prime generate by this code as same as mentioned in http://primes.utm.edu/lists/small/10000.txt . To check if n is prime or not, divide n by the numbers from 2 to sqrt(n) . If any of this range of number perfectly divides n then it's not prime.
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))
I have been working on find primes for about a year. This is what I found to be the fastest:
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(yx>p){ return true; }else if(x%yx ==0){ return false; } y = y.next; } return true; } }
1902465190909 nano seconds to get to 2147483629 starting at 2.
Here is my code which finds first 10,000 primes in 0.049655 sec on my laptop, first 1,000,000 primes in under 6 seconds and first 2,000,000 in 15 seconds
A little explanation. This method uses 2 techniques to find prime number
- first of all any non-prime number is a composite of multiples of prime numbers so this code test by dividing the test number by smaller prime numbers instead of any number, this decreases calculation by atleast 10 times for a 4 digit number and even more for a bigger number
- secondly besides dividing by prime, it only divides by prime numbers that are smaller or equal to the root of the number being tested further reducing the calculations greatly, this works because any number that is greater than root of the number will have a counterpart number that has to be smaller than root of the number but since we have tested all numbers smaller than the root already, Therefore we don't need to bother with number greater than the root of the number being tested.
Sample output for first 10,000 prime number
https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0 https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk
Here is the code in C language, Enter 1 and then 10,000 to print out the first 10,000 primes.
Edit: I forgot this contains math library ,if you are on windows or visual studio than that should be fine but on linux you must compile the code using -lm argument or the code may not work
Example: gcc -Wall -o "%e" "%f" -lm
#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 ?\n"); // this question helps in setting the limits on m or n value ie l or o printf(" Enter 1 or 2 to get anwser of first or second question\n"); // decision making do { printf(" -->"); scanf("%c",&d); while ((w=getchar()) != '\n' && w != EOF); if ( d == '1') { printf("\n 2. Enter the target no. of primes you will like to find from 3 to 2,000,000 range\n -->"); scanf("%10d",&l); o=INT_MAX; printf(" Here we go!\n\n"); break; } else if ( d == '2' ) { printf("\n 2.Enter the limit under which to find prime numbers from 5 to 2,000,000 range\n -->"); scanf("%10d",&o); l=o/log(o)*1.25; printf(" Here we go!\n\n"); break; } else printf("\n Try again\n"); }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\n%10dnd:%10d\n%10drd:%10d\n",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\n",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 !!\n"); end = clock(); cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC; printf(" Time taken : %lf sec\n",cpu_time_used); }
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(); } } }
