CareerCup

I guess following is optimized code for finding prime..which is certainly not O(N^2)

import java.util.ArrayList;
import java.util.List;

public class PrimeFinder {
    public int findNthPrime(int n) {
        if (n < 0) {
            throw new RuntimeException("Invalid argument :" + n);
        }
        List<Integer> primeNoList = new ArrayList<Integer>();
        int primeNo = 2;
        primeNoList.add(primeNo);
        boolean iterateOverPrimeNoList = true;
        int primeListCnt = 0;
        int num = primeNo + 1;
        int denominator = primeNo;
        int primeCnt = 0;
        while (primeCnt < n) {
            System.out.println("main loop interation cnt : " + primeCnt);
            primeListCnt = 0;
            iterateOverPrimeNoList = true;
            // check if next num is not divisible by all prime numbers which are
            // less than equal to sqrt of num
            while (primeListCnt < primeNoList.size() && iterateOverPrimeNoList) {
                denominator = primeNoList.get(primeListCnt);
                System.out.println("check num :" + num + " divisible by : " + denominator);
                if (num % denominator == 0) {
                    num++;
                    primeListCnt = 0;
                } else {
                    denominator = (primeListCnt + 1) < primeNoList.size() ? primeNoList.get(primeListCnt + 1) : denominator;
                    if (denominator <= Math.sqrt(num)) {
                        primeListCnt++;
                    } else {
                        iterateOverPrimeNoList = false;
                    }
                }

            }

            primeCnt++;
            primeNoList.add(num);
            primeNo = num;
            System.out.println(primeCnt + " nth Prime no:" + num + " found ");
            num++;

        }
        System.out.println(primeNoList);
        return primeNo;
    }

    public static void main(String[] args) {
        System.out.println(new PrimeFinder().findNthPrime(10));
    }
}

this is the most optimized code i could think of....

am a fresher so would like a review
thank you

public class nth_prime_no {

	public static void main(String... args){
		int n = 0;
		
		
		int j =3;
		int count=0;
		
		Scanner s=new Scanner(System.in);
		System.out.println("enter the position of prime no");
		n=s.nextInt();
		int pn[] =new int[n];
		pn[0]=2;
		for(int i=1;i<n;i++){
			while(j>=3){
				for(int k=0;k<i;k++)
					if(j%pn[k]==0)
						count++;
			
					
			if(count==0){
				pn[i]=j;
				break;
			}
			j++;
			count=0;	
		}
		
		
	}
	System.out.println("nth prime no is"+pn[n-1]);
	}

}

#include<stdio.h>
#include<conio.h>

int main()
{
int n=0,i=0,j=0,count=0,flag=0;

printf("\nwhich prime number you want ?? ");
scanf("%d",&n);

i=1;
do
{
i++;
flag=0;
for(j=2;j<i;j++)
{
if(i%j == 0)
{
flag=1;
break;
}
}

if(flag == 0)
count++;
}while(count != n);

printf("%d is prime number you wanted !! ",i);
getch();
return 0;
}

package PractiseApps;
import java.util.*;
import java.lang.*;
public class NthPrime {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner s = new Scanner(System.in);
		int N = s.nextInt();
		int i=3;
		N--;
		boolean flag = true;
		if (N<0){
			System.out.print(2);
		}
		else{
			while(true){
				int j=2;
				while(j<=Math.sqrt(i)){
					if(i%j==0)
						{
							flag=false;
							break;
						}
					j++;
				}
				if(flag)
					{
					N--;
					if (N<0){
						System.out.print(i);
						break;
					}
				}
			i++;
			flag = true;
			}
		}
	}

}

One way would be the using the sieve of eratosthenes and then simply looking up the number in the result. The algorithm can run in O(N), but the naive implementation runs in O(N^2) I think.

Another way (wwwDOTpaul-scottDOTcomSLASHnth-primeDOTphp) would be to actually count all the primes. For every odd number n (since evens can't be prime after 2) iterate through all primes up until sqrt(n) and see if they are a factor of the new number, if you find one the number is not prime, else it is so increment your count and keep looking until you've found enough primes. Since there are approximately logN prime numbers (I think?) that would involve N*logN calculations (since you try to divide every number by the logN primes you've found so far).

Use trial division rather than the sieve. This is due to the fact that you don't know the value N will be and you cant know the number of values you will need to mark in order to find it so this is infinitely large. Rather find the primes in order till you get to N. Use the previous primes to help you find future primes by trial division.

I think the following algo should work.

1. Compute the primes using sieve of Eratosthenes, upto m. Set m initially to a small number as 2 or 3.
2. If n < m then return the nth prime else set m = m^2 and repeat steps 1 & 2, each time re-using the previously computed sieve.

The following optimizations can be done
1> Prime numbers apart from 2 are all odd numbers
2> To check whether a number is prime it suffices to check numbers from 2 to sqrt of number
3> Any number can be broken down to product of prime factors

So while iterating to find nth prime number over the range of numbers, we need to consider only odd numbers greater than 2 and also for any number to check if its prime we need to check if its divisible without remainder by all prime numbers less equal to square root of the number.

Please suggest if we can have further improvement.

Assuming same function called multiple times

import java.util.Vector;

/*
 * To get the nth prime number , say if n=0, return 2, n=1, return 3 and so on
 * 
 *  Here i am using the scenario where same function might be called multiple times during single execution
 *  Not handled Exception is range of int
 */

public class PrimeTester {
	private static Vector<Integer> objVector = new Vector<Integer>();
	
	
	public static int getnthPrime(int n)
	{
		
		if( n < 0 )
			throw new IllegalArgumentException("Illegal Arument = " + n);
		
		//Now check if the objVector has already the prime number. Consider the scenario when same call is made multiple times
		if( objVector == null || objVector.size()==0)
		{
			objVector.add(2);
			objVector.add(3);
		}
	
		int intVectorSize = objVector.size();
		if ( intVectorSize > n )
			return objVector.get(n);
		
		//Keep on finding prime numbers till n is meet
		//Find next prime
		int item = objVector.get(intVectorSize-1);
		while ( intVectorSize <= n )
		{
			item = item + 2;
			if(isPrime(item))
			{
				objVector.add(item);
				intVectorSize++;
			}
		}
			
		return objVector.get(intVectorSize-1);
	}
	
	
	private static boolean isPrime(int item)
	{
		for (int i=0 ; i < objVector.size(); i++)
		{
			if( (item%(objVector.get(i))) == 0 )
				return false;
		}
		return true;
	}
	
}

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;


/**
 * CALCULATE THE NTH PRIME NUMBER
 * 
 * @author Jeyabarani K S
 *
 */
public class Prime {
	
	public static Map<Integer, Boolean> table = new TreeMap<Integer, Boolean>();
	
	public boolean isNumberPrime(int number) {
		
		if (number<2) {
			return false;
		} else if (number==2) {
			return true;
		} else if (number%2==0) {
			return false;
		} else {
			
			if(checkIfNumberPresentInTable(number)) {
				return table.get(number);
			} else { 
				// only need to check till its square root ... since atleast one divisor (if exist) should be less than the square root of the number 
				int tmp = (int) Math.sqrt(number);
				
				while(tmp>2) {
					
					if(tmp%2==0)
						tmp--;
					
					if(number%tmp==0) {
						table.put(number, false);
						return false;
					}
					
					tmp = tmp -2;
					
				}
				
				table.put(number, true);
				return true;
			}
		}
		
	}
	
	public int calculateNthPrimeNumber(int n) {
		
		int answer = 0;
		
		if (n>1) {
			answer = 1;
			while(n>0) {
				answer++;
				if(isNumberPrime(answer)) {
					n--;
				}				
			}
		}
		
		return answer;
	}
	
	private boolean checkIfNumberPresentInTable(int number){
		if (table.containsKey(number))
			return true;
		else 
			return false;
	}
	
	public static void main(String args[]) {
		Prime prime = new Prime();
		
		// calculate nth prime number
		System.out.println(prime.calculateNthPrimeNumber(7));	
		
		System.out.println();
		System.out.println();
				
		// prints the primes less than 100
		for(int i=0; i<100; i++) {
			if(prime.isNumberPrime(i))
				System.out.print(" " + i);
		}
		
	}
	
	

}

The most optimized code I can think of.

The key point is establish a list of primes and fill it until the size increase to n.
And I add 2 to num at a time as odd numbers can't be prime numbers.

int findNthPrime( int N ){

	int prime = 2;
	int num = 3;
	
	list<int> primes;
	primes.push_back(2);
	
	while( primes.size() < N){
	
		
		for( list<int>::iterator it = primes.begin(); it != primes.end() && *it <= (int) sqrt( num ); it++ ){
		
			if( num%(*it) == 0 ){
				num += 2;
				it = primes.begin();
			}
		}
		
		primes.push_back(num);
		
		num += 2;
	}
	
	return primes[N];
}

Time Complexity O(n2) and Space Complexity O(n) but very few computations.
Basic Logic: Prime No greater than 3 are of the form (6n-1) or (6n+1) and
The given number is a prime number if it is not divisible by any prime number less than its square root

public int findNthPrime(int N){
		// Prime No greater than 3 are of the form (6n-1) or (6n+1)
		// Cover base case of 2 and 3
		if(N < 0){
			return -1;
		}if(N == 0){
			return 2;
		}else if(N == 1){
			return 3;
		}

		List<Integer> primeNumbers = new ArrayList<Integer>();
		primeNumbers.add(2);
		primeNumbers.add(3);
		
		int count = 2;
		// The given number is a prime number if it is not divisible by 
		// any prime number less than its square root
		int lastIndex = 0;
		while(count <= N){
			int n = (6*(lastIndex+1)-1);
			int m  = n +2;
			int sqrt = (int) Math.sqrt(n);
			for(int i : primeNumbers){
				if(i > sqrt){
					primeNumbers.add(n);
					count++;
					break;	// Prime number found!
				}
				if(n%i == 0){
					break;  // Not a prime number
				}
			}
			if(count <= N) {
				sqrt = (int) Math.sqrt(m);
				for(int i : primeNumbers){
					if(i > sqrt){
						primeNumbers.add(m);
						count++;
						break;	// Prime number found!
					}
					if((m)%i == 0){
						break;  // Not a prime number
					}
				}
			}
			lastIndex++;
		}
		return primeNumbers.get(primeNumbers.size() - 1);
	}

public static int nthPrime(int n) {
        if(n == 0)
            return 2;
        if(n == 1)
            return 3;
        if(n == 2)
            return 5;
        boolean[] a = new boolean[n*n];

        a[2] = true;

        int k = 0;
        int i = 2;
        while(i < a.length) {
            if(!a[i])  {
                k++;
            }
            if(k == n)
                return i;
            for(int j = 2; j <= i && j*i < a.length; j++)
                a[i * j] = true;
            i++;
        }
        return i - 1;
    }

package interv.eBay;

import java.util.ArrayList;

public class FindNPrimeNumbers {

public static void main(String[] args) {
FindNPrimeNumbers fpN = new FindNPrimeNumbers();
ArrayList<Integer> output = fpN.findNprimes(7);
for(int i: output)
System.out.print(i+" ");
}

private ArrayList<Integer> findNprimes(int n) {
// TODO Auto-generated method stub
if (n <= 0)
return null;
else {
ArrayList<Integer> output = new ArrayList<Integer>();
output.add(2);
n--;
boolean isPrime =true;
int currentTestNumber = 3;
while (n > 0) {
for (int i : output) {
isPrime = true;
if (i > Math.sqrt(currentTestNumber))
break;
else if (currentTestNumber % i == 0) {
isPrime = false;
break;
}
}
if(isPrime)
output.add(currentTestNumber);
currentTestNumber +=2;
n--;
}
return output;
}

}

}