Primality by trial division: Difference between revisions
→{{header|Prolog}}: generate or test
(Updated all D entries) |
(→{{header|Prolog}}: generate or test) |
||
Line 1,556:
=={{header|Prolog}}==
The following predicate showcases Prolog's support for writing predicates suitable for both testing and generating. In this case, assuming the Prolog implemenation supports indefinitely large integers, prime(N) can be used to generate primes until memory is exhausted.
<lang Prolog>prime(2).
prime(N) :-
between(3, inf, N),
M is floor(sqrt(N+1)), % round-off paranoia ▼
1 is N mod 2
Max is (M-1) // 2, % integer division
</lang>
Example using SWI-Prolog:
<pre>?- time( (bagof( P, (prime(P), ((P > 100000, !, fail); true)), Bag),
length(Bag,N),
last(Bag,Last),
writeln( (N,Last) ) )).
% 1,724,404 inferences, 1.072 CPU in 1.151 seconds (93% CPU, 1607873 Lips)
Bag = [2, 3,
N = 9592,
▲ forall( between(S2,M2,X), N mod (2*X+1) > 0 ).
Last = 99991.
?- time( prime(99991) ).
% 165 inferences, 0.000 CPU in 0.000 seconds (92% CPU, 1213235 Lips)
true.
?-</pre>
=={{header|PureBasic}}==
| |||