我有一个问题要打印一百万个素数。我已经为此编写了一个java程序。。目前大约需要1.5分钟来计算。。我认为我的解决方案没有那么有效。我使用了以下算法：
- 最初将1 2 3添加到素数列表
- 计算要检查的数字的最后一位
- 检查数字是0、2、4还是6或8，然后跳过数字
- 否则计算数字的平方根
- 尝试将从2开始的数字除以该数字的平方根
- 如果数字是可整除的，则跳过该数字，否则将其添加到素数列表中
我也读过其他几个解决方案，但没有找到一个好的答案。请在理想情况下建议计算该值的最短时间，以及需要进行哪些更改才能使算法更高效。
如果您在列表中添加了1，则您的答案已经是错误的：)
无论如何，Erathosthenes筛是你应该开始的地方，它非常简单，非常有效。
一旦你熟悉了筛子的概念及其工作原理，你就可以继续使用阿特金筛，它有点复杂，但显然更有效。
关键事项：
- 跳过所有偶数。从5开始，一次只加两个
- 1不是素数
- 通过找到所有素数的模，直到该数的平方根，来测试一个数。除了素数，不需要测试任何东西
一个简单的埃拉托斯梯尼筛子像拍板一样运行。这将在不到一秒钟的时间内计算出我的盒子上的第100000个素数：
class PrimeSieve
{
public List<int> Primes;
private BitArray Sieve;
public PrimeSieve(int max)
{
Primes = new List<int> { 2, 3 }; // Must include at least 2, 3.
Sieve = new BitArray(max + 1);
foreach (var p in Primes)
for (var i = p * p; i < Sieve.Length; i += p) Sieve[i] = true;
}
public int Extend()
{
var p = Primes.Last() + 2; // Skip the even numbers.
while (Sieve[p]) p += 2;
for (var i = p * p; i < Sieve.Length; i += p) Sieve[i] = true;
Primes.Add(p);
return p;
}
}
编辑：筛选最佳从p^2开始，而不是像Will Ness正确指出的那样从2p开始(所有低于p^2的化合物编号将在早期迭代中标记)。
您可能想要实现埃拉托斯特内斯筛算法，以找到从1到n的素数，并在需要时迭代增加范围。(即，尚未找到1000000个素数)
首先，1不是素数。
其次，第一百万素数是15485863，因此您需要为一些大型数据处理做好准备。
第三，你可能想使用埃拉托斯梯尼筛；这里有一个简单的版本：
function sieve(n)
bits := makeArray(0..n, True)
for p from 2 to n step 1
if bits[p]
output p
for i from p*p to n step p
bits[i] := False
这可能不适用于计算前一百万个素数所需的数组大小。在这种情况下，您将希望实现Eratosthenes的分段筛。
我在博客上做了很多关于素数的工作，包括一篇文章，它提供了一个优化的埃拉托斯尼筛，并用五种编程语言实现。
无论你做什么，使用任何编程语言，你都应该能够在几秒钟内计算出前一百万个素数。
这里有一个Ocaml程序，它实现了Trial除法筛选(正如Will正确指出的那样，这是Eratosthenes的逆)：
(* Creates a function for streaming integers from x onward *)
let stream x =
let counter = ref (x) in
fun () ->
let _ = counter := !counter + 1 in
!counter;;
(* Filter the given stream of any multiples of x *)
let filter s x = fun () ->
let rec filter' () = match s () with
n when n mod x = 0 ->
filter' ()|
n ->
n in
filter' ();;
(* Get next prime, apply a new filter by that prime to the remainder of the stream *)
let primes count =
let rec primes' count' s = match count' with
0 ->
[]|
_ ->
let n = s () in
n :: primes' (count' - 1) (filter s n) in
primes' count (stream 1);;
它处理一个整数流。每次发现新的素数时，都会在流中添加一个滤波器，以便对流的其余部分进行该素数的任何倍数的滤波。此程序也可以更改为按需生成素数。
在Java中采用同样的方法应该相当容易。
希望这能有所帮助！
这里有一个javascript解决方案，它使用递归和迭代来达到第一百万素数。它没有Erathosthenes筛那么快，但不需要事先知道第一百万素数的值(即所需筛的大小)：
function findPrimes(n, current, primes) {
if (!n || current < 2) return []
var isPrime = true
for (var i = 0; i < primes.length; i++) {
if (current % primes[i] == 0) {
isPrime = false
break
}
}
if (isPrime) primes.push(current)
if (primes.length < n) return findPrimes(n, current + 1, primes)
else return primes
}
var primes = [2,3]
for (var i = 1; i <= 1000; i++) {
primes = findPrimes(i*1000, primes[primes.length - 1]+1, primes)
console.log(i*1000 + 'th prime: ' + primes[primes.length-1])
}
process.exit()
输出：
...
996000th prime: 15419293
997000th prime: 15435941
998000th prime: 15452873
999000th prime: 15469313
1000000th prime: 15485863
Process finished with exit code 0
作为一个更新鲜的级别，我会尝试这个级别，因此任何使其更高效、更快的改进都将受到的赞赏
public static void main(String ar[]) {
ArrayList primeNumbers = new ArrayList();
for(int i = 2; primeNumbers.size() < 1000000; i++) {//first 1 million prime number
// for(int i = 2; i < 1000000; i++) {//prime numbers from 1 to 1 million
boolean divisible = false;
for(int j=2;j<i/2;j++){
if((i % j) == 0) {
divisible = true;
break;
}
}
if(divisible == false) {
primeNumbers.add(i);
// System.out.println(i + " ");
}
}
System.out.println(primeNumbers);
}
- 最初向素数列表添加1 2 3
实际上，只要2个就足够了。硬编码3最多可以节省一毫秒。没有必要反复强调1。我确信把它包括在内是一个诚实的错误。你已经知道了，并且参与这个项目会有助于证实这一点。
- 计算要检查的数字的最后一位
最后一位？在什么基地？基数10？我想这可能是你的问题。
- 检查数字是0、2、4还是6或8，然后跳过数字else计算数字的平方根
我认为这就是问题所在。你的程序应该简单地跳过偶数，因为除了−2和2之外，它们都是复合的。另一方面，这不会使运行时间减半，因为像91和2209这样的奇数可能需要更多的努力才能被排除为非素数。
- 尝试将从2开始的数字除以该数字的平方根如果数字是可整除的，则跳过该数字，否则将其添加到素数列表中
是否"2直到数字"0"的平方根；包括4、6和9这样的数字？唯一需要检查的潜在因素是已经被证明是素数的数字。如果n不能被7整除，它也不能被49整除。如果你正在建立一个列表，你不妨用它来检查潜在的素数。
基准测试Java有点困难，因为您要受运行时系统的支配。然而，一分半钟，虽然梅森认为这是奇迹，但今天太慢了。五秒，十秒，我觉得可以接受。
也许这是应该避免使用对象而使用基元数组的情况之一。我的初稿比你的还要长。最终我想到了这个：
static int[] fillWithPrimes(int quantity) {
int[] primes = new int[quantity];
primes[0] = 2;
int currPi = 1;
int currIndex = 0;
int currNum = 3;
int currPrime;
boolean coPrimeFlag;
double squareRoot;
while (currPi < quantity) {
squareRoot = Math.sqrt(currNum);
do {
currPrime = primes[currIndex];
coPrimeFlag = (currNum % currPrime != 0);
currIndex++;
} while (coPrimeFlag && currPrime <= squareRoot);
if (coPrimeFlag) {
primes[currPi] = currNum;
currPi++;
}
currNum += 2;
currIndex = 0;
}
return primes;
}
然后我写了一个main()，它记录了调用fillWithPrimes()之前的时间，quantity参数为1000000，并报告了结果：
运行：
操作耗时2378毫秒
第10个素数是29
第100个素数是541
第1000个素数是7919
第10000个素数是104729
第100000个素数是1299709
1000000th prime是15485863
构建成功(总时间：2秒)
我相信它可以进一步优化。就我个人而言，我对两秒半感到满意。
不是所有5之后的东西都以5结尾，也可以被5整除吗，所以你可以跳过正确的东西(1，麻木)<>"5"，例如987985。我在Excel中做了一个，它将测试一百万个素数，并在大约15秒内将它们吐到一列中，但大约1500万会变得疯狂