Successive prime differences: Difference between revisions

<lang prolog>prime(2).

prime(N):-

N /\ 1 > 0, % odd

M is floor(sqrt(N)) - 1, % reverse 2*I+1

Max is M // 2, % integer division

forall(between(1, Max, I), N mod (2*I+1) > 0).

primesByDiffs([],_,[]).

primesByDiffs([Prime|Primes], Diff, [Slide|Slides]):-

length(Diff, Len0),

Len is Len0 + 1,

length(Slide, Len),

append(Slide, _, [Prime|Primes]),

select(Diff, Slide),!,

primesByDiffs(Primes, Diff, Slides).

primesByDiffs([_|Primes], Diff, Slides):-

primesByDiffs(Primes, Diff, Slides).

select([],_).

select([Diff|Diffs],[S1, S2|Stail]):-

S2 is S1 + Diff,

select(Diffs, [S2|Stail]).

run([],_).

run([Diff|Dtail], PrimeList):-

statistics(runtime,[Start|_]),

primesByDiffs(PrimeList, Diff, SlideList),

length(SlideList, Num),

statistics(runtime,[Stop|_]),

Runtime is Stop - Start,

SlideList = [First|SlideTail],

format('~|~w~t~7+ number: ~|~t~d~4+ [time(ms) ~|~t~d~3+] first: ~|~w~t~22+',[Diff, Num, Runtime, First]),

writeLast(SlideTail),!, nl,

run(Dtail, PrimeList).

writeLast([]).

writeLast(SlideTail):-

last(SlideTail, Last),

format('last: ~w',[Last]).

do:- Num is 1000000,

statistics(runtime,[Start|_]),

numlist(2, Num, List),

include(prime, List, PrimeList),

length(PrimeList, NumPrimes),

statistics(runtime,[Stop|_]),

RunTime is Stop - Start,

format('there are ~w primes until ~w [time(ms) ~w]~n',[NumPrimes, Num, RunTime]),

DiffList = [[1], [2], [2,2], [2,4], [4,2], [2,4,6],

[2,6,4], [4,2,6], [4,6,2], [6,2,4], [6,4,2]],

run(DiffList, PrimeList).</lang>

{{out}}

<pre>?- do.

there are 78498 primes until 1000000 [time(ms) 14614]

[1] number: 1 [time(ms) 123] first: [2,3]

[2] number: 8169 [time(ms) 124] first: [3,5] last: [999959,999961]

[2,2] number: 1 [time(ms) 131] first: [3,5,7]

[2,4] number: 1393 [time(ms) 133] first: [5,7,11] last: [999431,999433,999437]

[4,2] number: 1444 [time(ms) 133] first: [7,11,13] last: [997807,997811,997813]

[2,4,6] number: 279 [time(ms) 141] first: [17,19,23,29] last: [997097,997099,997103,997109]

[2,6,4] number: 297 [time(ms) 141] first: [29,31,37,41] last: [979541,979543,979549,979553]

[4,2,6] number: 162 [time(ms) 142] first: [67,71,73,79] last: [980587,980591,980593,980599]

[4,6,2] number: 300 [time(ms) 141] first: [19,23,29,31] last: [997099,997103,997109,997111]

[6,2,4] number: 159 [time(ms) 142] first: [1601,1607,1609,1613] last: [997091,997097,997099,997103]

[6,4,2] number: 306 [time(ms) 142] first: [31,37,41,43] last: [997141,997147,997151,997153]

true.

</pre>