为什么我的 Seive of Eratosthenes 算法实现 运行 进入无限循环？

Question

我正在实施 Sieve 的算法来查找最多 n 个素数。我无法找出为什么 运行 进入无限循环。

这里我给出了代码片段。请帮忙

for(int j=2;j<=Math.sqrt(n);j++){
  if(a[j]==true){
     int x=0;
     for(int p=(j*j+x*j); p<=n;x++){
        a[p]=true;
     }
  }
}   

Answer 1

您的内部循环正在检查 p 但从未更改它

Answer 2

一些优化建议：

// When j is 2, the bitwise (2 & 1) will be 0, so the cycle increments by 1
// When j is odd (from 3 and above), the cycle goes in steps of 2 
// (thus exploring only odd numbers)
// As a result, this cycle is twice as faster than the one progressing
// in increments of 1 
// See here --------------------V
for(int j=2;j<=Math.sqrt(n);j+=(j & 1 ? 2 : 1)) {
  if(a[j]==true){
     // int x=0; // what for?
     // a sum is cheaper than a multiplication
     // Here --V and here --V
     for(int p=j*j; p<=n;p+=j){
        a[p]=true;
     }
  }
}