CODEWITHSUNDEEP
javaperformancealgorithmcomplexity-theoryprimes
codewarrior
codewarrior

Reputation: 1034

find nth prime number

I've written the following code below to find the nth prime number. Can this be improved in time complexity?

Description:

The ArrayList arr stores the computed prime numbers. Once arr reaches a size 'n', the loop exits and we retrieve the nth element in the ArrayList. Numbers 2 and 3 are added before the prime numbers are calculated, and each number starting from 4 is checked to be prime 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's 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));
    }
}

Upvotes: 3

Views: 17876

Answers (4)

Youssef
Youssef

Reputation: 11

    System.out.println("Enter The number n: ");
    Scanner scanner = new Scanner(System.in);

    int n = scanner.nextInt();

    int x = 0;
    String prime = "";

    for (int i = 1; i <= n; i++) {

        int counter = 0;

        for (x = i; x >= 1; x--) {

            if (i % x == 0) {
                counter++;
            }
        }

        if (counter == 2){
            prime =  prime + i + " ";
        }

    }

    System.out.println(prime);
}

}

Upvotes: 0

Deepanshu Rathore
Deepanshu Rathore

Reputation: 1

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

Upvotes: 0

xvorsx
xvorsx

Reputation: 2442

Yes.

Your algorithm make O(n^2) operations (maybe I'm not accurate, but seems so), where n is result.

There are http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes algorithm that takes O(ipn* log(log(n))). You can make only inp steps in it, and assume that n = 2ipn*ln(ipn). n just should be greater then ipn-prime. (we know distributions of prime numbers http://en.wikipedia.org/wiki/Prime_number_theorem)

Anyway, you can improve 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));
    }
}

Upvotes: 10

xpda
xpda

Reputation: 15813

A few things you can do to speed it up:

  1. Start counter at 5 and increment it by 2 instead of 1, then don't check mod 2 in the loop.
  2. Instead of starting temp at counter / 2, start it at the first odd <= int(sqrt(counter))
  3. decrement temp by 2.

I'm not sure whether it counts as improving complexity, but (2) above will go from O(n^2) to O(n*sqrt(n))

Upvotes: 2

Related Questions