nonprime(n)

["Ruud H.G. van Tol" <rvtol@isolution.nl>]

nonprime(n) = { my(k=0); while(n-(n-=k-(k=primepi(n))), ); n }
\\ (after M.F.Haslers code in https://oeis.org/A002808)

? [ nonprime(n) |n<-[0..20] ]
% [0, 1, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 
28, 30]

See also: forcomposite.


To compare:

? default()
   parisize = 2147483648
   primelimit = 9999999

? for(n=1,2^18, prime(n));
cpu time = 1,516 ms, real time = 1,521 ms.

? for(n=1,2^18, nonprime(n));
cpu time = 1,911 ms, real time = 1,915 ms.


? for(n=1,2^19, prime(n));
cpu time = 8,084 ms, real time = 8,101 ms.

? for(n=1,2^19, nonprime(n));
cpu time = 4,556 ms, real time = 4,566 ms.

-- Ruud