fork(5) download
copy 
  1. sieve(N, [2|PS]) :-       % PS is list of odd primes up to N
  2.     retractall(mult(_)),
  3.     sieve_O(3,N,PS).
  4.  
  5. sieve_O(I,N,PS) :-        % sieve odds from I up to N to get PS
  6.     I =< N, !, I1 is I+2,
  7.     (   mult(I) -> sieve_O(I1,N,PS)
  8.     ;   (   I =< N / I -> 
  9.             ISq is I*I, DI  is 2*I, add_mults(DI,ISq,N)
  10.         ;   true 
  11.         ),
  12.         PS = [I|T],
  13.         sieve_O(I1,N,T)
  14.     ).
  15. sieve_O(I,N,[]) :- I > N.
  16.  
  17. add_mults(DI,I,N) :-
  18.     I =< N, !,
  19.     ( mult(I) -> true 
  20.     ; assert(mult(I)) ),
  21.     I1 is I+DI,
  22.     add_mults(DI,I1,N).
  23. add_mults(_,I,N) :- I > N.
  24.  
  25. main(N) :- current_prolog_flag(verbose,F),
  26.   set_prolog_flag(verbose,normal), 
  27.   time( sieve( N,P)), length(P,Len), last(P, LP), writeln([Len,LP]),
  28.   set_prolog_flag(verbose,F).
  29.  
  30. :- dynamic( mult/1 ).
  31. :- main(100000), main(1000000).
Success #stdin #stdout #stderr 1.87s 6204KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[9592, 99991]
[78498, 999983]
stderr
copy 
% 293,176 inferences, 0.14 CPU in 0.14 seconds (102% CPU, 2094114 Lips)
% 3,122,303 inferences, 1.67 CPU in 1.70 seconds (98% CPU, 1869643 Lips)
https://ideone.com/WDC7z
language:
Prolog (swi 7.6.4)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!