Re: My prime counting function
On Sun, 3 Aug 2008 21:43:24 -0700 (PDT), Andrew Thompson
<andrewthommo@gmail.com> wrote:
No, it's just I don't care, not until you post an
SSCCE (written in Java, to bring this rot 'on-topic').
I am not James, but I did write a prime counting program based on his
ideas. Not quite an SSCCE as it uses a couple of functions from my
own maths library.
rossum
//----- Start Code ------
import mjrutilities.Maths;
// This provides two/three functions:
// long iSqrt(long num)
// int iSqrt(int num)
// which both return the int (long) square root of
// the given number.
// and
// int nthPrime(int n)
// which returns the nth prime number.
import java.util.HashMap;
import java.util.Map;
/**
* <p>Title: PrimeCount</p>
*
* <p>Description: gives an exact count of the primes less than or
equal to a given number:<br>
*
* pi(1) = 0<br>
* pi(2) = 1<br>
* pi(10 = 4<br>
* pi(100) = 25<br>
* pi(1000) = 168</p>
*
* Comments from original version:
*
* -----------------------------------------
*
* Written by James S. Harris. Copyright (c) 2002-2003. All rights
reserved.
*
* My suggestion is to write your own version modifying this one.
* Commercial use is not permitted without my written permission.
*
* Proper attribution might get me some credit for having found the
prime counting function
* So play with this and share, and *please* mention where you got
it from.
*
* -----------------------------------------
*
* @author Martin Ross, based on JSH
* @version 1.0
* @date August 2007
*/
public class PrimeCount {
private PrimeCount() { }
/**
* Calculates pi(limit) [the number of primes up to limit] for
* a long value of limit.
*
* @param limit how far to count primes.
* @return the number of primes up to limit.
*/
public static long pi(long limit) {
long retVal = 0L;
if (limit < Integer.MAX_VALUE) {
retVal = pi((int)limit);
} else {
// Have to do it the hard way
if (limit % 2 == 1) { ++limit; } // Evens only
long limRoot = Maths.iSqrt(limit);
long level = Math.min(limRoot, pi(limRoot));
retVal = P(limit, level);
} // end if
return retVal;
} // end pi(long)
/**
* Calculates pi(limit) [the number of primes up to limit] for
* an int value of limit.
*
* @param limit how far to count primes.
* @return the number of primes up to limit.
*/
public static int pi(int limit) {
if (limit < 2) { return 0; }
if (limit == 2) { return 1; }
// Use even limit - halves data storage.
if (limit % 2 == 1) { ++limit; }
int retVal = 0;
if (limit < 17) {
switch (limit) {
case 4:
retVal = 2;
break;
case 6:
retVal = 3;
break;
case 8: case 10:
retVal = 4;
break;
case 12:
retVal = 5;
break;
case 14: case 16:
retVal = 6;
break;
default:
throw new IllegalStateException("PrimeCount.pi
invalid internal value of limit parameter.");
} // end switch
} else if (limit < KNOWN_SIZE &&
knownCounts.containsKey(limit)) {
// We have seen this number before
retVal = knownCounts.get(limit);
} else {
// Have to do it the hard way
if (limit % 2 == 1) { ++limit; }
int limRoot = Maths.iSqrt(limit);
int level = Math.min(limRoot, pi(limRoot));
retVal = P(limit, level);
if (limit < KNOWN_SIZE) { knownCounts.put(limit, retVal);
}
} // end if
return retVal;
} // end pi(int)
/**
* this is the inner recursive function - int version.
*/
private static int P(int x, int n) {
// Adjust n
if (needToCheck(x, n)) {
n = Math.min(n, pi(Maths.iSqrt(x)));
} // end if
// P(x, n) = x - 1 - sum for i=1 to n of {P([x/p_i],i-1) -
// (i-1)}
// I have adjusted for j = 0 to n-1. MJR
int sum = 0;
for (int j = 0; j < n; ++j) {
sum += P(x / Maths.nthPrime(j + 1), j) - j;
} // end for
return x - 1 - sum;
} // end P(int, int)
/**
* this is the inner recursive function - long version.
*/
private static long P(long x, long n) {
if (x < Integer.MAX_VALUE && n < Integer.MAX_VALUE) {
return P((int)x, (int)n);
} // end if
// Adjust n
if (needToCheck(x, n)) {
n = Math.min(n, pi(Maths.iSqrt(x)));
} // end if
// P(x, n) = x - 1 - sum for i=1 to n of {P([x/p_i],i-1) -
// (i-1)}
// I have adjusted for j = 0 to n-1. MJR
long sum = 0;
if (n > Integer.MAX_VALUE) {
throw new IndexOutOfBoundsException("PrimeCount.P n too
large for integer counter.");
} // end if
for (int j = 0; j < n; ++j) {
sum += P(x / Maths.nthPrime(j + 1), j) - j;
} // end for
return x - 1 - sum;
} // end P(long, long)
/**
* Determines if we need to compare n and pi(iSqrt(x))
* May avoid some additional recursion.
*/
private static boolean needToCheck(long x, long n) {
switch ((int)n) {
case 8: return x <= 361;
case 7: return x <= 289;
case 6: return x <= 169;
case 5: return x <= 121;
case 4: return x <= 49;
case 3: return x <= 25;
case 2: return x <= 9;
case 1: return x <= 4;
default: return true;
} // end switch
} // end needToCheck()
// Keep small values - uses lazy evaluation.
private final static int KNOWN_SIZE = 1000;
private static Map<Integer, Integer> knownCounts = new
HashMap<Integer, Integer>(KNOWN_SIZE / 2);
/**
* code to test prime counting.
*
* @param args not used.
*/
public static void main(String[] args) {
for (int i = 0; i < 1001; i += 50) {
System.out.println("pi(" + i + ") = " + PrimeCount.pi(i));
} // end for
System.out.println();
long target = 1;
for (int j = 1; j < 11; ++j) {
target *= 10L;
System.out.println("pi(10^" + j + ") = " +
PrimeCount.pi(target));
} // end for
System.out.println("Complete.");
} // end main()
} // end class PrimeCount
//----- End Code ------