打印第 N 个素数的代码

Question

我必须打印第 N 个素数。例如：
第一个质数是2
第二个质数是 3
.
.
第 10 个素数是 29 等等....

我的算法如下：
1) 将 2 和 3 添加到堆栈中。
2) 如果 n <= 栈的大小，获取位置 n 的项目并输出 answer
3) 否则，从栈的最后一个元素开始，检查是否为 prime
4) 要检查素数，请从堆栈中的每个元素中除以。如果堆栈中任何元素的余数为 0，则不是质数。打破循环
5) 如果是 Prime，添加到堆栈
6) 只搜索奇数

我的代码是：

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

此代码突然停止工作而没有给出任何 output.What 是我的代码中的缺陷吗？

Answer 1

int a[number]; 是错误的，因为 number 不是常量。相反，你想把它写成 int *a=new int[number]

Answer 2

你的循环逻辑有问题。您需要尝试将 i 除以堆栈中从 0 到 top 的所有数字，并且仅当 i 可以被 [=30= 整除时]其中你增加了个数。如果它不能被它们中的任何一个分割，那么你正在增加它。

所以，改变逻辑来测试i是否能被a[j]整除。如果是，则跳出循环。如果你到达循环的末尾 (j == top) 并且它还没有成功地除掉它们中的任何一个，那么你就知道它是素数并且你可以增加 count。此外，将计数与 top 进行比较的检查应该在 j 循环之外（即在完成所有试验划分之后）

    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++;
                a[++top] = i;
                break;
            }
        }
        if (count == number) {
            cout << a[top];
            break;
        }
    }

编辑：您还需要将 count 初始化为 2，而不是 0，以说明 2 和 3。

打印第 N 个素数的代码

Code to print Nth prime number

c++

algorithm

primes