I have another comparison on a problem I worked on recently. http://www.jsoftware.com/jwiki/Essays/Semiprimes A semiprime is a number with exactly 2 (not necessarily distinct) prime factors.
The number of semiprimes less than n can be computed as: nplt=: p:^:_1 NB. #primes < n plt =: i.&.(p:^:_1) NB. primes < n nsp =: 3 : '+/ (nplt@(>.@(y&%)) - [EMAIL PROTECTED]) plt >.%:y' " 0 In the semiprime page in MathWorld http://mathworld.wolfram.com/Semiprime.html the solution for the number of semiprimes less than or equal to n is given as: pi<sup>(2)</sup>(x)=sigma(k=1,pi(sqrt(n))) [pi(n/p<sub>k</sub>-k+1] I can not do the formula justice here; you have to look at it on that MathWorld webpage to see it properly laid out. The derivation for the J computation is given as: It is possible to produce this list without testing each integer i<n . A semiprime can be written as a product of primes p*q where p<:q . p is necessarily less than >.%:n , and for each such p the possible primes q are those greater than or equal to p but less than >.n%p . The MathWorld page doesn't give the derivation, but says: where pi(x) is the prime counting function and p_k is the kth prime (R. G. Wilson V, pers. comm., Feb. 7, 2006; discovered independently by E. Noel and G. Panos around Jan. 2005, pers. comm., Jun. 13, 2006). ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
