primesalgol

# Is this program to find prime numbers wrong?

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`, 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.

Solution

• ``````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.