Primality by trial division: Difference between revisions
→{{header|Picat}}: Split into subsections.
(→{{header|Picat}}: Split into subsections.) |
|||
Line 3,053:
=={{header|Picat}}==
===Iterative===
* imperative: is_prime1/1 (0.971)▼
<lang Picat>is_prime1(N) => ▼
* recursive: is_prime2/1 (3.258s)▼
* functional: is_prime3/1 (0.938s)▼
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.▼
▲is_prime1(N) =>
if N == 2 then
true
Line 3,080 ⟶ 3,064:
N mod I > 0
end
end.</lang>
===Recursive===
<lang Picat>is_prime2(N) =>
(N == 2 ; is_prime2b(N,3)).
Line 3,095 ⟶ 3,079:
;
is_prime2b(N,Div+2)
).</lang>
<lang Picat>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).</lang>
===Generator approach===
{{trans|Prolog}}
▲% prime2(N) can be used to generate primes until memory is exhausted
<lang Picat>prime2(2).
▲% 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),
Line 3,118 ⟶ 3,102:
Max is (M-1) // 2, % integer division
foreach(I in 1..Max) N mod (2*I+1) > 0 end.</lang>
===Test===
▲<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.</lang>
{{out}}
Line 3,128 ⟶ 3,123:
[100000,9592]
[1000000,78498]</pre>
===Benchmark===
▲Times
▲* imperative: <code>is_prime1/1</code> (0.971)
▲* recursive: <code>is_prime2/1</code> (3.258s)
▲* functional: <code>is_prime3/1</code> (0.938s)
* test/generate <code>prime2/1</code> (2.129s)
=={{header|PicoLisp}}==
| |||