Clever Geek Handbook

Find nth prime number

I wrote the following code below to find the nth prime number. Could this be improved in time complexity?

Description:

ArrayList arr stores computed primes. When arr reaches size 'n', the loop ends and we return the nth element in the ArrayList. The numbers 2 and 3 are added before the primes are calculated, and each number starting with 4 is checked for simplicity or not.

public void calcPrime(int inp) {
    ArrayList<Integer> arr = new ArrayList<Integer>(); // stores prime numbers 
                                                      // calculated so far
    // add prime numbers 2 and 3 to prime array 'arr'
    arr.add(2); 
    arr.add(3);

    // check if number is prime starting from 4
    int counter = 4;
     // check if arr size has reached inp which is 'n', if so terminate while loop
    while(arr.size() <= inp) {
        // dont check for prime if number is divisible by 2
        if(counter % 2 != 0) {
            // check if current number 'counter' is perfectly divisible from 
           // counter/2 to 3
            int temp = counter/2;
            while(temp >=3) {
                if(counter % temp == 0)
                    break;
                temp --;
            }
            if(temp <= 3) {
                arr.add(counter);
            }
        }
        counter++;
    }

    System.out.println("finish" +arr.get(inp));
    }
}
+3


source to share


3 answers


Yes.

Your algorithm does O (n ^ 2) operations (I may not be precise, but it seems so) where n .

There is an algorithm http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes that takes O (ipn * log (log (n))) . You can only take inp steps and assume n = 2ipn * ln (ipn) . n must be greater than ipn -prime. (we know the distributions of prime numbers http://en.wikipedia.org/wiki/Prime_number_theorem )



Anyway, you can improve the existing solution:

public void calcPrime(int inp) {
    ArrayList<Integer> arr = new ArrayList<Integer>();
    arr.add(2);
    arr.add(3);

    int counter = 4;

    while(arr.size() < inp) {
        if(counter % 2 != 0 && counter%3 != 0) {
            int temp = 4;
            while(temp*temp <= counter) {
                if(counter % temp == 0)
                    break;
                temp ++;
            }
            if(temp*temp > counter) {
                arr.add(counter);
            }
        }
        counter++;
    }

    System.out.println("finish" +arr.get(inp-1));
    }
}
+10


source


Several things you can do to speed up this:

  • Start the counter in increments of 5 and increment it by 2 instead of 1, then don't check mod 2 in a loop.
  • Instead of running temp at counter / 2, run it on the first odd <= int (sqrt (counter))
  • Decrease the tempo by 2.


I'm not sure if this counts as an improvement in complexity, but (2) above will go from O (n ^ 2) to O (n * sqrt (n))

+2


source 


public static void Main()
    {
        Console.Write("Enter a Number : ");
        int num;
        int[] arr = new int[10000];
        num = Convert.ToInt32(Console.ReadLine());
        int k;
        k = 0;
        int t = 1;
        for (int j = 1; j < 10000; j++)
        {
            for (int i = 1; i <= j; i++)
            {
                if (j % i == 0)
                {
                    k++;
                }
            }
            if (k == 2)
            {
                arr[t] = j;
                t++;
                k = 0; 
            }
            else
            { 
                k = 0;
            } 
        }
        Console.WriteLine("Nth Prime number. {0}", arr[num]);
        Console.ReadLine();
    }
0


source






More articles:


All Articles