Normally, when we need to find all prime numbers upto or less than user input N, we need total time complexity of **O(N*sqrt(N))**, because we use “trial division” to verify primality. Code as below in Java.

public int countPrimes(int N){ int count=0; for(int i=2; i<=N; i++) { //We choose sqrt(N), because if N isn't a prime, it should be equal to somewhat A * B, //A should be less or equal to square root of N //B should be greater or equal to square root of N //Therefore, we only need to check j up to square root of N for (int j = 2; j <= Math.sqrt(N); j++) { if (i % j != 0) { count++; } } } return count; }

Now, we have a better way, "Sieve of Eratosthenes" ! (Very hard to pronounce, isn't it ! )

public int countPrimesSieveEratosthenes(int N){ int count = 0; int[] primes = new int[N]; for (int i = 0; i < N ; i++) { primes[i] = 1; } primes[0]=0; primes[1]=0; //This nested loop costs O(sqrt(N) * log(log(N))) //Normally, shrinking by a square root wil take your time complexity to O(log(log(N))) for (int i = 2; i <= Math.sqrt(N); i++) { if(primes[i] == 1){ for (int j = 2; i*j < N; j++) { primes[i*j] = 0; } } } for (int i = 0; i < primes.length; i++) { count += primes[i]; } return count; }

Therefore, this improved version gives us O(N) + O(sqrt(N) * log(log(N))) = **O(sqrt(N) * log(log(N)))**, improved from **O(N*sqrt(N))**. You can find more about algorithmic complexity from Wikipedia

Or you just want to check the number is prime, you also can do:

public void checkPrime(int num){ if(num==2){ System.out.println("Prime"); return; } if(num%2==0 || num==1){ System.out.println("Not prime"); return; } for(int i=3;i*i<=num; i+=2){ if(num%i==0){ System.out.println("Not prime"); return; } } System.out.println("Prime"); }

More about run time complexity O(log(log(N)))

You can also generate a compressed prime sieve using bit manipulation. The idea is that each bit represents a boolean value indicating whether a number is prime or not. This saves a lot of room when creating the sieve. In this implementation I store all odd numbers in individual longs meaning that for each long I use I can represent a range of 128 numbers (even numbers are omitted because they are not prime, with the exception of 2 which is handled as a special case).

CODE:

static final int NUM_BITS = 128;

// Sets the bit repesenting n to 1 indicating this number is not prime

static void setBit(long[] arr, int n) {

if ((n & 1) == 0) return; // n is even

arr[n / NUM_BITS] |= 1L << (n – 1) / 2;

}

// Returns true if a bit if turned on for the number n (AKA n is a prime)

// Make sure you DO NOT use this method to access numbers outside your prime sieve range!

static boolean isSet(long[] arr, int n) {

if (n == 2) return true; // two is prime

if ((n & 1) == 0) return false; // n is even

long chunk = arr[n / NUM_BITS];

long mask = 1L << (n – 1) / 2;

return (chunk & mask) != mask;

}

// Returns an array of longs with each bit indicating whether a number

// is prime or not. Use the isSet and setBit methods to toggle to bits for each number.

static long[] supremeprimesieve(int limit) {

final int num_chunks = (int) Math.ceil(limit / 128.0);

final int sqrt_limit = (int) Math.sqrt(limit);

// if (limit < 2) return 0; // uncomment for primeCount purposes

// int primeCount = (int) Math.ceil(limit / 2.0); // Counts number of primes <= limit

long[] chunks = new long[num_chunks];

chunks[0] = 1; // 1 as not prime

for (int i = 3; i <= sqrt_limit; i += 2)

if (isSet(chunks, i))

for (int j = i * i; j <= limit; j += i) // j+=i can overflow

if (isSet(chunks, j)) {

setBit(chunks, j);

// primeCount–;

}

return chunks;

}