Skip to content

Instantly share code, notes, and snippets.

@josephspurrier
Created August 25, 2015 16:30
Show Gist options
  • Save josephspurrier/9d7cfcad27266a9ba39c to your computer and use it in GitHub Desktop.
Save josephspurrier/9d7cfcad27266a9ba39c to your computer and use it in GitHub Desktop.
Prime Number Counter in Java
/*
I was able to achieve these speeds on my laptop: Intel Core i7-4500U @ 1.80GHZ
Test 1: 664579 took 56ms
Test 2: 5761455 took 702ms
Test 3: 50847534 took 9.062s
*/
public class PrimeCounter {
public static void main(String[] args) {
int[] times = new int[]{10000000, 100000000, 1000000000};
for (int i = 0; i < times.length; i++) {
long start = System.currentTimeMillis();
int num = countPrimes(times[i]);
long elapsed = System.currentTimeMillis() - start;
System.out.println("Test " + (i+1) + ": " + num +"\t took " + elapsed);
}
}
public static int countPrimes(int limit) {
// Return if less than 1
if (limit <= 1) {
return 0;
}
// Get the sqrt of the limit
double sqrtLimit = Math.sqrt(limit);
// Create array
boolean[] numbers = new boolean[limit];
// Set 1 to prime
numbers[0] = true;
int numPrimes = 0;
// Count the number of olds
if (limit%2 == 0) {
numPrimes = limit / 2;
} else {
numPrimes = (limit + 1) / 2;
}
for (int i = 3; i <= sqrtLimit; i+=2) {
if (!numbers[i]) {
for (int j = i * i; j < limit; j += i * 2) {
if (!numbers[j]) {
numbers[j] = true;
numPrimes -= 1;
}
}
}
}
return numPrimes;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment