primes - 这个寻找素数的程序错了吗？

Question

在阅读“代码：计算机的隐藏语言”时，我遇到了作者包含的 ALGOL 程序，该程序使用 Sieve 算法查找 10,000 以内的素数。下面是代码。

begin
   Boolean array a[2:10000];
   integer i, j;

   for i :=2 step 1 until 10000 do
       a[i] :=true;

   for i :=2 step 1 until 100 do
       if a[i] then 
            for j := 2 step 1 until 10000 / i do
                a[i*j] :=false;
   for i :=2 step 1 until 10000 do
       if a[i] then
           print(i);
end

当我通常看到一个程序时，我会使用真实值来测试它以查看它的有效性。在这种情况下，我担心的是 line For j:=....。如果我们以i3 和 3 作为步骤中的具体点j。则为j1。因此，a[i*j]即 ，a[3]当它应该为真时为假，因为它是素数。可以j或i等于1吗？

我在这里错过了什么吗？我将不胜感激任何帮助。

Answer 1

for j := 2
         ^

j从 2 开始，因此只有非素数的索引 (i*2, i*3, ...) 会false在数组中设置为。

Answer 2

如果有人对此感兴趣，可以稍微快一点地实现这个算法

#include <iostream>
#include <vector>
using namespace std;
long long sumPrime(long long n){
   
    vector<long long> isPrime(n+1,true);
    for (long long i = 2; i <= n; i++) {
        if(isPrime[i]){
            cout<<i<<" ";
        }
        for (long long j = i*i; j <= n; j=j+i) {
            isPrime[j]=false;
        }
    }
    
}



int main() {
    cout<<sumPrime(2000000);
    return 0;
}