Skip to content

Instantly share code, notes, and snippets.

@TobiasWooldridge
Last active August 29, 2015 14:19
Show Gist options
  • Save TobiasWooldridge/4ce60612bcb47ec4e75a to your computer and use it in GitHub Desktop.
Save TobiasWooldridge/4ce60612bcb47ec4e75a to your computer and use it in GitHub Desktop.
import java.util.ArrayList;
import java.util.BitSet;
/**
* Created by Tobias on 24/04/2015.
*/
public class Primes {
public static interface Solution {
String getAlgorithm();
int numPrimesBelow(int n);
}
// 0.4s
public static class SieveSolution implements Solution {
@Override
public String getAlgorithm() {
return "Sieve";
}
@Override
public int numPrimesBelow(int n) {
BitSet sieve = new BitSet(n + 1);
// assume everything is a prime
sieve.set(0, n);
// get rid of numbers before first actual prime (2)
sieve.clear(0);
sieve.clear(1);
// get rid of all multiples of primes
int primes = 0;
for (int i = 1; i < n; i++) {
if (sieve.get(i)) {
primes++;
int prime = i;
int val = prime + prime;
while (val < n) {
sieve.clear(val);
val += prime;
}
}
}
return primes++;
}
}
// ~3.0 seconds
public static class SqrtHistorySolution implements Solution {
@Override
public String getAlgorithm() {
return "Sqrt History";
}
@Override
public int numPrimesBelow(int n) {
ArrayList<Integer> primes = new ArrayList<Integer>();
if (n < 2) {
return 0;
}
primes.add(2);
for (int primeCandidate = 3; primeCandidate < n; primeCandidate++) {
boolean isPrime = true;
double sqrt = Math.ceil(Math.sqrt(primeCandidate));
for (Integer prime : primes) {
if (prime > sqrt) {
break;
}
if (primeCandidate % prime == 0) {
isPrime = false;
break;
}
}
if (isPrime) {
primes.add(primeCandidate);
}
}
return primes.size();
}
}
// ~30.7 seconds
public static class NaiveSqrtSolution implements Solution {
@Override
public String getAlgorithm() {
return "Naive Sqrt Solution";
}
private boolean isPrime(int n) {
if (n == 2) {
return true;
}
for (int i = 2; i <= Math.ceil(Math.sqrt(n)); i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
@Override
public int numPrimesBelow(int n) {
int primes = 0;
for (int i = 2; i < n; i++) {
if (isPrime(i)) {
primes++;
}
}
return primes;
}
}
public static void main(String[] args) {
Solution[] solutions = {
new SieveSolution(),
new SqrtHistorySolution(),
new NaiveSqrtSolution()
};
for (Solution s : solutions) {
long startTime = System.nanoTime();
int numPrimes = s.numPrimesBelow(10000000);
long endTime = System.nanoTime();
System.out.printf("Found %d primes in %d ms using %s\n", numPrimes, (endTime - startTime) / 1000000, s.getAlgorithm());
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment