Safe primes and unsafe primes: Difference between revisions
Add CLU
No edit summary |
Not a robot (talk | contribs) (Add CLU) |
||
Line 613:
Number of unsafe primes below 10,000,000: 633,922
</pre>
=={{header|CLU}}==
<lang clu>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
sieve = proc (n: int) returns (array[bool])
prime: array[bool] := array[bool]$fill(0,n+1,true)
prime[0] := false
prime[1] := false
for p: int in int$from_to(2, isqrt(n)) do
if prime[p] then
for c: int in int$from_to_by(p*p,n,p) do
prime[c] := false
end
end
end
return(prime)
end sieve
start_up = proc ()
primeinfo = record [
name: string,
ps: array[int],
maxps, n_1e6, n_1e7: int
]
po: stream := stream$primary_output()
prime: array[bool] := sieve(10000000)
safe: primeinfo := primeinfo${
name: "safe",
ps: array[int]$[],
maxps: 35,
n_1e6: 0,
n_1e7: 0
}
unsafe: primeinfo := primeinfo${
name: "unsafe",
ps: array[int]$[],
maxps: 40,
n_1e6: 0,
n_1e7: 0
}
for p: int in int$from_to(2, 10000000) do
if ~prime[p] then continue end
ir: primeinfo
if prime[(p-1)/2]
then ir := safe
else ir := unsafe
end
if array[int]$size(ir.ps) < ir.maxps then
array[int]$addh(ir.ps,p)
end
if p<1000000 then ir.n_1e6 := ir.n_1e6 + 1 end
if p<10000000 then ir.n_1e7 := ir.n_1e7 + 1 end
end
for ir: primeinfo in array[primeinfo]$elements(
array[primeinfo]$[safe, unsafe]) do
stream$putl(po, "First " || int$unparse(ir.maxps)
|| " " || ir.name || " primes:")
for i: int in array[int]$elements(ir.ps) do
stream$puts(po, int$unparse(i) || " ")
end
stream$putl(po, "\nThere are " || int$unparse(ir.n_1e6)
|| " " || ir.name || " primes < 1,000,000.")
stream$putl(po, "There are " || int$unparse(ir.n_1e7)
|| " " || ir.name || " primes < 1,000,000.\n")
end
end start_up</lang>
{{out}}
<pre>
First 35 safe primes:
5 7 11 23 47 59 83 107 167 179 227 263 347 359 383 467 479 503 563 587 719 839 863 887 983 1019 1187 1283 1307 1319 1367 1439 1487 1523 1619
There are 4324 safe primes < 1,000,000.
There are 30657 safe primes < 1,000,000.
First 40 unsafe primes:
2 3 13 17 19 29 31 37 41 43 53 61 67 71 73 79 89 97 101 103 109 113 127 131 137 139 149 151 157 163 173 181 191 193 197 199 211 223 229 233
There are 74174 unsafe primes < 1,000,000.
There are 633922 unsafe primes < 1,000,000.</pre>
=={{header|D}}==
| |||