c++ - 如何通过生成复合数来修复我的 Prime 生成程序

Question

我正在尝试用 C++ 编写一个程序，该程序将计算素数并将它们存储在一个数组中。考虑这是我的第三个代码。

我遇到的问题是，当我得到质数时，我也得到合数，特别是 5 和 7 的倍数（至少直​​到 30 的限制）。我知道，代码可能会很糟糕，但鉴于我在编码和素数方面的经验有限，我能想到的就是这样。

这是我写的：

#include <iostream>
int j;
int i = 3;
int prime[30];

int main()
{
    for (i; i < 30; i+=2)
    {
        for (j =i; j>i*i; j--)
        {
            if ((i % j) == 0)
            {
                continue;
            }
        }
        prime[i] = i;
        std::cout << prime[i] << std::endl;
    }
}

输出：3 5 7 9 11 13 15 17 19 21 23 25 27 29

标签： c++primes

Answer 1

您的内部循环只需要测试您迄今为止遇到的素数的可分性。（例如，如果您已经用 3 测试过整除性，那么用 9 测试整除性毫无意义）

int main()
{
    int j;
    int i = 3;
    int primes[30];
    int primecount = 0;

    primes[primecount++] = 2;  // hardcode 2, it's the only even number

    for (i = 3; i < 30; i += 2)
    {
        bool isPrime = true;

        for (j = 0; j < primecount; j++)
        {
            if ((i % primes[j]) == 0)
            {
                isPrime = false;
                break;
            }
        }
        if (isPrime)
        {
            primes[primecount++] = i;
        }
    }

    for (int k = 0; k < primecount; k++)
    {
        std::cout << primes[k] << " ";
    }
    std::cout << std::endl;
}