43 lines
1.1 KiB
Text
43 lines
1.1 KiB
Text
% Sieve of Erastothenes
|
|
% Returns an array [1..max] marking the primes
|
|
sieve = proc (max: int) returns (array[bool])
|
|
prime: array[bool] := array[bool]$fill(1, max, true)
|
|
prime[1] := false
|
|
|
|
for p: int in int$from_to(2, max/2) do
|
|
if prime[p] then
|
|
for comp: int in int$from_to_by(p*2, max, p) do
|
|
prime[comp] := false
|
|
end
|
|
end
|
|
end
|
|
return(prime)
|
|
end sieve
|
|
|
|
% Sum the digits of a number
|
|
digit_sum = proc (n: int) returns (int)
|
|
sum: int := 0
|
|
while n ~= 0 do
|
|
sum := sum + n // 10
|
|
n := n / 10
|
|
end
|
|
return(sum)
|
|
end digit_sum
|
|
|
|
start_up = proc ()
|
|
max = 500
|
|
po: stream := stream$primary_output()
|
|
|
|
count: int := 0
|
|
prime: array[bool] := sieve(max)
|
|
for i: int in array[bool]$indexes(prime) do
|
|
if prime[i] cand prime[digit_sum(i)] then
|
|
count := count + 1
|
|
stream$putright(po, int$unparse(i), 5)
|
|
if count//10 = 0 then stream$putl(po, "") end
|
|
end
|
|
end
|
|
|
|
stream$putl(po, "\nFound " || int$unparse(count) ||
|
|
" additive primes < " || int$unparse(max))
|
|
end start_up
|