C -当范围很大时如何求素数

Question

如何找到1到10^9之间的所有素数，我知道我们可以使用Sieve_of_Eratosthenes来寻找较小的范围，但是当范围太大相当于10^6时怎么办?

Answer 1

高达10^9并不是什么大问题。首先，只看奇数(因为只有一个偶数素数)。其次，使用位数组，因此您只需要5亿个比特或大约62兆字节。即使是简单的代码也应该在几秒钟内完成。

如果你更进一步，你将筛选从1到10^9的数字，然后从10^9 + 1到2 * 10^9，以此类推。大于10^13的时候就很有趣了你需要花更多的精力。