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 .