user6889367 user6889367 - 1 month ago 6
C++ Question

Code to print Nth prime number

I have to print the Nth prime number.
For example:

1st prime number is 2

2nd prime number is 3

.

.

10th prime number is 29 and so on....



My algorithm is as follows:

1) Add 2 and 3 to stack.

2) If n <= Size of stack, get item at position n and output answer

3) Else, start from last element of stack, check if prime

4) To check for prime, divide from each element in stack. If remainder 0 for any element in stack, not a prime. Break loop

5) If Prime, add to stack

6) Search only odd numbers


My code is :

#include <iostream>
using namespace std;

int main() {
int number, count = 0;
cin >> number; //position of prime number
int a[number];
a[0] = 2;
a[1] = 3;
int top = 1;
if (number <= 2) {
cout << a[number - 1] << endl;
} else {
for (int i = 5; i <= 10001; i += 2) {
for (int j = 0; j <= top; j++) {

if (i % a[j] != 0) {
count++;

}
if (count == (top + 1)) {
a[++top] = i;
if ((count + 1) == number) {
cout << a[top];
break;
}

}

}

}

}
return 0;
}


This code abruptly stops working without giving any output.What is the flaw in my code?

Answer

It's a problem with your looping logic. You need to trial divide i by all the numbers from 0 to top on your stack, and only if i is divisible by none of them do you increase count. As it is you are increasing it if it is indivisible by any of them.

So, change the logic to test ifi is divisible by a[j]. If it is, then break out of the loop. If you reach the end of the loop (j == top) and it hasn't successfully divided any of them then you know it's prime and you can increase count. Also, the check where you compare count to top + 1 should be outside of the j loop (i.e. after you have done all the trial divisions)

    for (int i = 5; i <= 10001; i += 2) {
        for (int j = 0; j <= top; j++) {
            if (i % a[j] == 0) {
                break;
            }
            if(j == top)
                count++;
        }
        if (count == (top + 1)) {
            a[++top] = i;
            if ((count + 1) == number) {
                cout << a[top];
                break;
            }
        }
    }