not a decent check
public static boolean isPrime(int number){
for (int divisor = 2; divisor <= (number/2); divisor++){
if (number % divisor == 0){
return false;
}
}
return true;
}
R. Sedgewick and K. Wayne trix
public class PrimeSieve {
public static void main(String[] args) {
int n = Integer.parseInt(args[0]);
boolean[] isPrime = new boolean[n+1];
for (int i = 2; i <= n; i++) {
isPrime[i] = true;
}
for (int factor = 2; factor*factor <= n; factor++) {
if (isPrime[factor]) {
for (int j = factor; factor*j <= n; j++) {
isPrime[factor*j] = false;
}
}
}
int primes = 0;
for (int i = 2; i <= n; i++) {
if (isPrime[i]) primes++;
}
System.out.println("The number of primes <= " + n + " is " + primes);
}
}
Copyright © 2000–2011, Robert Sedgewick and Kevin Wayne.
Last updated: Tue Aug 30 09:58:33 EDT 2016.
Latest comments (1)
I just wrote this up so i might remember it if I ever had to turn up on an interview... lolz