Almost prime: Difference between revisions
Content deleted Content added
Updated D entry |
Prolog |
||
Line 379:
say almost($_)[^10] for 1..5;</lang>
=={{header|Prolog}}==
<lang prolog>% almostPrime(K, +Take, List) succeeds if List can be unified with the
% first Take K-almost-primes.
% Notice that K need not be specified.
% To avoid having to cache or recompute the first Take primes, we define
% almostPrime/3 in terms of almostPrime/4 as follows:
%
almostPrime(K, Take, List) :-
% Compute the list of the first Take primes:
nPrimes(Take, Primes),
almostPrime(K, Take, Primes, List).
almostPrime(1, Take, Primes, Primes).
almostPrime(K, Take, Primes, List) :-
generate(2, K), % generate K >= 2
K1 is K - 1,
almostPrime(K1, Take, Primes, L),
multiplylist( Primes, L, Long),
sort(Long, Sorted), % uniquifies
take(Take, Sorted, List).
</lang>That's it. The rest is machinery. For portability, a compatibility section is included below.
<lang Prolog>% Define prime(N) so that it can be used both to test and to generate primes indefinitely.
prime(2).
prime(N) :-
generate(3, N),
1 is N mod 2, % odd
M is floor(sqrt(N+1)), % round-off paranoia
Max is (M-1) // 2,
forall( between(1, Max, I), N mod (2*I+1) > 0 ).
% nPrimes(+Count, ?Primes) is true iff Primes is a list of the first Count primes
% This predicate assume isPrime(_) is available for use.
nPrimes(Count, Primes) :-
Counter = counter(0),
retractall( isPrime(_) ),
prime(P),
assertz( isPrime(P) ),
arg(1, Counter, N0),
N is N0 + 1,
nb_setarg(1, Counter, N),
(N < Count -> fail
; bagof(B, isPrime(B), Primes),
retractall(isPrime(_))).
% multiply( +A, +List, Answer)
multiply( A, [], [] ).
multiply( A, [X|Xs], [AX|As] ) :-
AX is A * X,
multiply(A, Xs, As).
% multiplylist( L1, L2, List) succeeds if List is the concatenation of X * L2
% for successive elements X of L1.
multiplylist( [], B, [] ).
multiplylist( [A|As], B, List ) :-
multiply(A, B, L1),
multiplylist(As, B, L2),
append(L1, L2, List).
m(A,B,C) :- C is A*B.
take(N, List, Head) :-
length(Head, N),
append(Head,X,List).
</lang>
<lang Prolog>%%%%% compatibility section %%%%%:- if(current_prolog_flag(dialect, yap)).
generate(Min, I) :- between(Min, inf, I).
append([],L,L).
append([X|Xs], L, [X|Ls]) :- append(Xs,L,Ls).
:- endif.
:- if(current_prolog_flag(dialect, swi)).
generate(Min, I) :- between(Min, inf, I).
:- endif.
:- if(current_prolog_flag(dialect, gprolog)).
nb_setarg(Arg, Term, Value) :-
setarg( Arg, Term, Value, false). % no backtracking
generate(Min, I) :-
current_prolog_flag(max_integer, Max),
between(Min, Max, I).
:- endif.
</lang>
Example using SWI-Prolog:<pre>
?- time( (almostPrime(5, 10, L), writeln(L))).
[32,48,72,80,108,112,120,162,168,176]
% 1,630 inferences, 0.001 CPU in 0.010 seconds (7% CPU, 2393539 Lips)
</pre>
=={{header|Python}}==
| |||