c++ - 质数嵌套循环逻辑

Question

我目前正在处理如下所述的任务。我的问题是，为什么我的代码只将素数重复为 2 而不是其余数字。如果有人可以帮助我遍历逻辑以便我可以尝试解决解决方案，而不是直接发布答案，我将不胜感激。感谢所有人:)

编写一个程序，使用两个嵌套的 for 循环和模数运算符 (%) 检测并打印从 1 到 10,000 的素数。(素数是不能被整除的自然数除了他们自己和一个之外的任何其他数字)。显示所有找到素数。

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> n; // will store our values from 1-10000

    for (int i= 0; i < 10000; i++) { // vector loading
       n.push_back(i);
       n[i]= n[i] + 1;

       for (int j= 1; j < 10000  ; j++ ) { // Error is here?
           if (n[j] % j == 0) { // supposed to go through all the numbers 
                                // and flag the prime numbers
               cout<<n[i]  <<" is a prime";
               i++;
               break;
            }
        }
    }

    return 0;
}

Answer 1

简单的方法很容易理解。

1. 外层循环(假设这里的循环变量是num)从2到10000遍历，检查每一个数是否是质数。

2. 内循环(假设这里的循环变量是fact)通过form 2到num - 1

3. 通过 num % fact == 0 检查 num 是否有一个因子 fact。如果 fact 是 num 的因数，则中断内部循环并继续检查下一个数字。

4. 如果在检查了从 2 到 num - 1 的所有数字后，没有一个是 num 的因数，那么我们确定 num是质数，继续查下一个数。

请注意，0 和 1 是特殊情况，因此我们将它们排除在循环之外。

这个方法不需要任何数组。时间复杂度为O(n²)，空间复杂度为O(1)。

顺便说一句，这个问题还有其他更好的解决方案，例如Sieve of Eratosthenes .