While reading “Code: The Hidden Language of Computer,” I came across the ALGOL program that the author included to find the prime numbers through 10,000 using the Sieve algorithm. Below is the code.
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
When I usually see a program I test it by using real values to see its validity. In this case, the concern I have is with the line For j:=..... If we take i as 3 and 3 as the specific point in the steps of j. Then j would be 1. So, a[i*j], i.e., a[3], would be false when it should be true since its a prime. Can j or i be equal to 1?
Am I missing something over here? I would appreciate any help.
for j := 2
^
j starts at 2, so only non-prime numbers' indexes (i*2, i*3, ...) would be set to false in the array.