Sequence of primes by trial division: Difference between revisions

=={{header|Prolog}}==

Creates a 2,3,5 factorization wheel to eliminate the majority of divisors and prime candidates before filtering.

<lang Prolog>

wheel235(L) :-

W = [6, 4, 2, 4, 2, 4, 6, 2 | W],

lazy_list(accumulate, 1/W, L).

accumulate(M/[A|As], N/As, N) :- plus(M, A, N).

roll235wheel(Limit, A) :-

wheel235(W),

append(A, [N|_], W),

N > Limit, !.

prime235(N) :- % N is prime excepting multiples of 2, 3, 5.

wheel235(W),

wheel_prime(N, W).

wheel_prime(N, [D|_]) :- D*D > N, !.

wheel_prime(N, [D|Ds]) :- N mod D =\= 0, wheel_prime(N, Ds).

primes(Limit, [2, 3, 5 | Primes]) :-

roll235wheel(Limit, Candidates),

include(prime235, Candidates, Primes).

</lang>

{{Out}}

<pre>

?- primes(100, L), write(L).

[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]

L = [2, 3, 5, 7, 11, 13, 17, 19, 23|...].

?- primes(1000, L), length(L, N), last(L, X).

L = [2, 3, 5, 7, 11, 13, 17, 19, 23|...],

N = 168,

X = 997.

</pre>