Эта программа, чтобы найти простые числа неправильно?

Question

Читая "Код: скрытый язык компьютера", я наткнулся на программу ALGOL, которую автор включил, чтобы найти простые числа через 10000 с использованием алгоритма Sieve. Ниже приведен код.

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

Когда я обычно вижу программу, я проверяю ее, используя реальные значения, чтобы увидеть ее достоверность. В этом случае меня беспокоит линия For j:=...., Если мы возьмем i 3 и 3 в качестве конкретной точки на этапах j, затем j будет 1. Итак, 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;
}