Primality by trial division: Difference between revisions
→{{header|Picat}}
m (→{{header|Quackery}}: typo, again) |
|||
Line 3,051:
}
?></lang>
=={{header|Picat}}==
Four different versions:
* imperative: is_prime1/1 (0.971)
* recursive: is_prime2/1 (3.258s)
* functional: is_prime3/1 (0.938s)
* testing and generating: prime2/1 (2.129s) {{trans|Prolog}}
Times are for calculating the number of primes below 10, 100,1_000,10_000, 100_000, and 1_000_000 respectively.
<lang Picat>go =>
println([I : I in 1..100, is_prime1(I)]),
nl,
foreach(P in 1..6)
Primes = [ I : I in 1..10**P, is_prime1(I)],
println([10**P,Primes.len])
end,
nl.
% iterative
is_prime1(N) =>
if N == 2 then
true
elseif N <= 1 ; N mod 2 == 0 then
false
else
foreach(I in 3..2..ceiling(sqrt(N)))
N mod I > 0
end
end.
% recursive
is_prime2(N) =>
(N == 2 ; is_prime2b(N,3)).
is_prime2b(N,_Div), N <= 1 => false.
is_prime2b(2,_Div) => true.
is_prime2b(N,_Div), N mod 2 == 0 => false.
is_prime2b(N,Div), Div > ceiling(sqrt(N)) => true.
is_prime2b(N,Div), Div > 2 =>
(N mod Div == 0 ->
false
;
is_prime2b(N,Div+2)
).
% Functional
is_prime3(2) => true.
is_prime3(3) => true.
is_prime3(P) => P > 3, P mod 2 =\= 0, not has_factor3(P,3).
has_factor3(N,L), N mod L == 0 => true.
has_factor3(N,L) => L * L < N, L2 = L + 2, has_factor3(N,L2).
% Translation of Prolog version.
% prime2(N) can be used to generate primes until memory is exhausted
%
% Difference from Prolog implementation: Picat does not support between/3 with
% "inf" as upper bound, so a high number (here 2**156+1) must be used.
prime2(2).
prime2(N) :-
between(3, 2**156+1, N),
N mod 2 = 1, % odd
M is floor(sqrt(N+1)), % round-off paranoia
Max is (M-1) // 2, % integer division
foreach(I in 1..Max) N mod (2*I+1) > 0 end.</lang>
{{out}}
<pre>[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
[10,4]
[100,25]
[1000,168]
[10000,1229]
[100000,9592]
[1000000,78498]</pre>
=={{header|PicoLisp}}==
| |||