质数嵌套循环逻辑

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

有几个问题，但对于初学者来说，请考虑第一个循环。

i = 0
n.push_back(i);       // Now n[0] is now valid (having the value 0)
n[0] = n[0] + 1;      // Now n[0] is still valid (having the value 1)
j = 1;
if (n[j] % j == 0)    // Ups... access to n[1] which is invalid
                      // as you have only pushed one element, i.e. n[0]

Answer 2

简单的方法比较容易理解。

外层循环（假设这里的循环变量为num）从2到10000遍历，检查每一个数是否为质数。
内循环（假设这里的循环变量为fact）通过形式2到num - 1
检查 num 是否有因数 fact by num % fact == 0。如果fact是num的因数，则打破内循环，继续检查下一个数。
如果检查完从2到num - 1的所有数，其中none是num的因数，则可以肯定num是质数，继续查下一个数。

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

此方法不需要任何数组。时间复杂度为 O(n²) 并且 space 复杂度为 O(1).

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

Answer 3

内循环不需要遍历整个范围，内循环可能的值是从2开始到<=那个数字/2.

Like if you want to check whether 99 is prime or not then you need to set inner loop from 2 to 49 (99 / 2 is the max possible factor for that number) so do not iterate through the rest all.

So if you iterate inner loop from 2 to 98 then it's meaning less to iterate this loop after 49, think about it.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    //vector<int> n; // will store our values from 1-10000
    int flag  =0;
    for (int i= 2; i < 10000; i++) // vector loading
    {
        //n.push_back(i);
        //n[i]= n[i] + 1;
        flag  =0;
        for (int j= 2; j <= i / 2  ; j++ ) 
        {
            if (i % j == 0)             
            {
                flag = 1;
                break;
            }

        }
        if(flag == 0)
        {
            cout << "%d number is Prime" << i;
        }
    }
return 0;
}

Answer 4

了解循环的目的

外循环是提供数字的循环，因此你不需要矢量
内部循环是进行检查的循环

你在哪里打印？

内部循环检查一个数是否不是素数。唯一的办法知道这是外循环提供的数字是否 not 可以被内循环提供的任何数字整除。因此内循环不打印任何东西，因为它必须在知道一个数字是素数之前用尽所有检查
您的打印语句应该放在最后。这意味着它应该在内循环之后但仍在外循环内并且它应该根据内循环发现的内容打印数字如果它是质数。所以你应该有办法知道内部循环是否找到素数

最后请注意，内部循环必须从 2 开始并在 i - 1 结束，因为每个数字都可以被 1 和它本身整除

质数嵌套循环逻辑

Prime number nested loop Logic

c++

primes

c++11

了解循环的目的

你在哪里打印？