Skip to main content

Prime Numbers

Problem : Given a number, determine if it is prime or not.

To determine if a given number is prime or not, you have to check if the given number is divisible by any number other than 1 and itself. If it is, then it is not a prime number. 

* In this algorithm, we check if the given number is less than or equal to zero. If it is then it is not a prime number. 

* Next we check to see if the given number is 2.  2 is the only even prime number. 

* Then we check if the given number is even. If it is, then it is not a prime number. 

* Lastly we divide the given number starting from 3 till the square root of the given number. 

  /**
     * This method checks if the given number n is a prime number or not.
     *
     * @param n - The number to be checked.
     * @return boolean
     */
    public static boolean isPrime(int n)
    {
        if (n <= 1)
        {
            return false;
        }

        if (n == 2)
        {
            return true;
        }

        if (n % 2 == 0)
        {
            return false;
        }


        int m = (int) Math.sqrt(n);

        for (int i = 3; i <= m; i += 2)
        {
            if (n % i == 0)
            {
                return false;
            }
        }

        return true;
    }

This algorithm has a time complexity of O ( n ) and a space complexity of O ( 1 ).

============================================

Problem : Given an integer n, generate all the prime numbers till n.

This solution uses the isPrime discussed above. 

* In this solution we first create an array of boolean of size n + 1 and fill the array with true. 

* We then know that zero and one are not prime numbers. Hence we mark the first 2 entries to be false.

* Next we start with 2 and then set all multiples of 2 less than the given number to false. At this point, 2 is a prime number and all multiples of 2 are marked false.
   
This is repeated in a loop with increments of 1 till we hit a number lesser than the square root of the given number. So at the end of the second iteration, 3 will be true indicating it is prime and all of it's multiples are marked false and so on.
   

  /**
     * This generates the prime numbers using Sieve of Eratosthenes.
     * @param n
     */
    public static void generatePrime(int n)
    {
        boolean[] isPrime = new boolean[n+1];

        Arrays.fill(isPrime, true);

        isPrime[0] = false;
        isPrime[1] = false;

        for (int i = 2; i <= (int) Math.sqrt(n); i++)
        {
            if (isPrime[i])
            {
                for (int j = i * i; j <= n; j += i)
                {
                    isPrime[j] = false;
                }
            }
        }

        System.out.println("Prime numbers till " + n + " are : \n");

        for (int i = 0; i <>
        {
            if (isPrime[i])
            {
                System.out.println(i);
            }
        }
    }
Labels:

Comments

Post a Comment

Popular posts from this blog

Even Integer Iterator

Problem : Given an iterator of integers, can you give me back another iterator which iterates over the given iterator of integers such that the new iterator gives only even integers. There a couple of different ways to solve this problem. * The first option is to create a new list of integers and add only the even integers from the given iterator and then return an iterator by calling list.iterator(). This has a time complexity of O (n) but also has a space complexity of O (n) in the worst case, which is not desirable. Here is the code for it - public static Iterator<Integer> giveEvenIntegersIterator(Iterator<Integer> iterator) { List<Integer> evenIntegers = new ArrayList<Integer>(); if (iterator != null) { while(iterator.hasNext()) { Integer number = iterator.next(); if (number != null && number % 2 == 0) { evenIntegers.add(number); } } } retu
Post a Comment
Read more

Sum of Subsets - Find how many pairs in the given array sum to a given number

Problem : Given an array of integers intArray[] and another integer sum, find how many pairs of numbers in the given array will sum up to the given sum. This problem is one of the most sought after question in interviews. There may be slight variations of this problem. There are many ways to solve this problem. The most efficient solution considering both time and space complexity is the one discussed below - /** * This will find how many pairs of numbers in the given array sum * up to the given number. * * @param array - array of integers * @param sum - The sum * @return int - number of pairs. */ public static int sumOfSubset(int[] array, int sum) {          // This has a complexity of O ( n lg n )         Arrays.sort(array);         int pairCount = 0;         int leftIndex = 0;         int rightIndex = array.length - 1;          // The portion below has a complextiy of         //  O ( n ) in the worst case.         while (array[rightIndex] >= su
Post a Comment
Read more

Minimum Maximum Stack

Problem : Design a stack of Numbers which will give you the minimum and maximum of all the elements it contains. This problem is also known as MinStack or MaxStack problem which expects you to find only the minimum or maximum. It is restated here to capture both. A stack typically has push(), pop() and size() operations. In order to find the minimum and the maximum, we will need to iterate over the elements of the stack each time we want to find the minimum and maximum. This will result in O (n) time complexity. And typically stack does not let us iterate over the elements. Many do not know that the java.util.Stack implementation does allow it as it extends java.util.Vector. We can make it more efficient by storing the minimum and maximum as instance variables in our stack and update them when ever we push a new number on to the stack. This will result in O(1) complexity for updating the max and min when pushing new numbers on stack, but when we pop the number which is currently set a
Post a Comment
Read more