Better way to find all prime numbers less than N & time complexity O(log(log(N)))

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)))

One thought on “Better way to find all prime numbers less than N & time complexity O(log(log(N)))

  1. William Fiset

    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;
    }

Leave a Reply