Find adjacent primes which differ by a square integer: Difference between revisions
Content added Content deleted
m (→{{header|jq}}: fix comment) |
Not a robot (talk | contribs) (Add CLU) |
||
Line 171: | Line 171: | ||
return 0; |
return 0; |
||
}</lang> |
}</lang> |
||
=={{header|CLU}}== |
|||
<lang clu>% Integer square root |
|||
isqrt = proc (s: int) returns (int) |
|||
x0: int := s/2 |
|||
if x0=0 then return(s) end |
|||
x1: int := (x0 + s/x0)/2 |
|||
while x1 < x0 do |
|||
x0 := x1 |
|||
x1 := (x0 + s/x0)/2 |
|||
end |
|||
return(x0) |
|||
end isqrt |
|||
% See if a number is square |
|||
% Note that all squares are 0, 1, 4, or 9 mod 16. |
|||
is_square = proc (n: int) returns (bool) |
|||
d: int := n//16 |
|||
if d=0 cor d=1 cor d=4 cor d=9 then |
|||
return(n = isqrt(n)**2) |
|||
else |
|||
return(false) |
|||
end |
|||
end is_square |
|||
% Find all primes up to a given number |
|||
sieve = proc (top: int) returns (array[int]) |
|||
prime: array[bool] := array[bool]$fill(2,top-1,true) |
|||
for p: int in int$from_to(2,isqrt(top)) do |
|||
if prime[p] then |
|||
for c: int in int$from_to_by(p*p,top,p) do |
|||
prime[c] := false |
|||
end |
|||
end |
|||
end |
|||
list: array[int] := array[int]$predict(1,isqrt(top)) |
|||
for p: int in int$from_to(2,top) do |
|||
if prime[p] then array[int]$addh(list,p) end |
|||
end |
|||
return(list) |
|||
end sieve |
|||
start_up = proc () |
|||
MAX = 1000000 |
|||
DIFF = 36 |
|||
po: stream := stream$primary_output() |
|||
primes: array[int] := sieve(MAX) |
|||
for i: int in int$from_to(array[int]$low(primes)+1, |
|||
array[int]$high(primes)) do |
|||
d: int := primes[i] - primes[i-1] |
|||
if d>DIFF cand is_square(d) then |
|||
stream$putright(po, int$unparse(primes[i]), 6) |
|||
stream$puts(po, " - ") |
|||
stream$putright(po, int$unparse(primes[i-1]), 6) |
|||
stream$puts(po, " = ") |
|||
stream$putright(po, int$unparse(d), 4) |
|||
stream$puts(po, " = ") |
|||
stream$putright(po, int$unparse(isqrt(d)), 4) |
|||
stream$putl(po, "^2") |
|||
end |
|||
end |
|||
end start_up</lang> |
|||
{{out}} |
|||
<pre> 89753 - 89689 = 64 = 8^2 |
|||
107441 - 107377 = 64 = 8^2 |
|||
288647 - 288583 = 64 = 8^2 |
|||
368021 - 367957 = 64 = 8^2 |
|||
381167 - 381103 = 64 = 8^2 |
|||
396833 - 396733 = 100 = 10^2 |
|||
400823 - 400759 = 64 = 8^2 |
|||
445427 - 445363 = 64 = 8^2 |
|||
623171 - 623107 = 64 = 8^2 |
|||
625763 - 625699 = 64 = 8^2 |
|||
637067 - 637003 = 64 = 8^2 |
|||
710777 - 710713 = 64 = 8^2 |
|||
725273 - 725209 = 64 = 8^2 |
|||
779477 - 779413 = 64 = 8^2 |
|||
801947 - 801883 = 64 = 8^2 |
|||
803813 - 803749 = 64 = 8^2 |
|||
821741 - 821677 = 64 = 8^2 |
|||
832583 - 832519 = 64 = 8^2 |
|||
838349 - 838249 = 100 = 10^2 |
|||
844841 - 844777 = 64 = 8^2 |
|||
883871 - 883807 = 64 = 8^2 |
|||
912167 - 912103 = 64 = 8^2 |
|||
919511 - 919447 = 64 = 8^2 |
|||
954827 - 954763 = 64 = 8^2 |
|||
981887 - 981823 = 64 = 8^2 |
|||
997877 - 997813 = 64 = 8^2</pre> |
|||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |