user6889367 - 1 year ago 82

C++ Question

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;

}

Answer Source

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 if`i`

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;
}
}
}
```