J
Jussi Piitulainen
JSH said:
Below is an implementation of your algorithm (for Java's long type)
based on your description of it, as quoted above. A couple of things
were not immediately clear to me from reading your description: first,
sqrt(x) must mean floor(sqrt(x)); second, you don't mention the base
case of the recursion; third, the significance of n when less than
floor(sqrt(x)) is lost to me, but I guess that does not matter.
I used x < 2 as the base case, with the value 0. I think the else
branch in primeCount(x, n) mirrors your description transparently;
prime(i) implements something that can reasonably be called a sieve;
and floorSqrt(m) uses straight binary search.
The main method prints useful diagnostics for zero or one arguments,
and P(x, n) when given x and n; java -cp . P 100 100 produces the
number of primes 25 and the diagnostic information that it pooled 4
primes for the result, so at least that case works as you say.
import java.util.List;
import java.util.ArrayList;
class P {
public static void main(String [] args) {
if (args.length == 0) {
System.out.println("Long.MAX_VALUE == "
+ Long.MAX_VALUE);
System.out.print("floorSqrt(Long.MAX_VALUE) == "
+ floorSqrt(Long.MAX_VALUE));
System.out.print((floorSqrt(Long.MAX_VALUE) < Integer.MAX_VALUE)
? " < "
: " > ");
System.out.print("Integer.MAX_VALUE == ");
System.out.println(Integer.MAX_VALUE);
System.out.print("First ten primes:");
for (int i = 1 ; i <= 10 ; ++ i) {
System.out.print(' ');
System.out.print(prime(i));
}
System.out.println();
}
else if (args.length == 1) {
long x = Long.valueOf(args[0]);
System.out.println("floorSqrt(" + x + ") == "
+ floorSqrt(x));
}
else if (args.length == 2) {
long x = Long.valueOf(args[0]);
long n = Long.valueOf(args[1]);
System.out.println("primeCount(" + x + ", " + n + ") == "
+ primeCount(x, n));
System.out.println("prime pool size: " + knownPrimes.size());
}
else throw new IllegalArgumentException();
}
static long primeCount(long x, long n) {
if (x < 2) {
// to avoid infinite recursion - primeCount(1,0) ok?
return 0;
}
else {
long s = floorSqrt(x);
long c = primeCount(s, s);
if (n > c) {
return primeCount(x, c);
}
else {
long sum = 0;
for (int i = 1 ; i <= n ; ++ i) {
sum += primeCount(x/prime(i), i - 1) - (i - 1);
}
return x - 1 - sum;
}
}
}
// (CEILING - 1)*(CEILING - 1) < Long.MAX_VALUE < CEILING*CEILING
private static final long CEILING = (long)Math.sqrt(Long.MAX_VALUE) + 1;
private static long floorSqrt(long m) {
if (m < 0) throw new IllegalArgumentException();
long below = 0;
long above = CEILING;
while (below + 1 < above) {
long middle = (below + above)/2;
// below < middle < above
if (middle * middle > m) {
above = middle;
}
else {
below = middle;
}
}
// below*below <= m < (below + 1)*(below + 1)
return below;
}
private static final List<Long> knownPrimes = new ArrayList<Long>();
static { knownPrimes.add(2L); }
private static long prime(int i) { // prime(1) == 2
for (int k = knownPrimes.size() ; k < i ; ++ k) {
long n = knownPrimes.get(k - 1);
while (divides(knownPrimes, n)) {
++ n;
}
knownPrimes.add(n);
}
return knownPrimes.get(i - 1);
}
private static boolean divides(List<Long> ms, long n) {
for (int k = 0 ; k < ms.size() ; ++ k) {
if (n % ms.get(k) == 0) {
return true;
}
}
return false;
}
}