数字3、5和7不显示为质数

Question

我需要创建一个在两个输入数之间生成质数的函数。我通过测试范围内每个数字的质数来做到这一点。问题是数字3、5或7从不显示。我不知道出了什么问题。

下面是我测试一个数的质数的方法：

bool isPrime(int number){
    using namespace std;
    if((number%2==0) || (number%3==0) || (number%4==0) || (number%5==0) ||
       (number%6==0) || (number%7==0) || (number%8==0) || (number%9==0))
    {
        return false;
    }
    else if ((number/1==number) && (number/number==1))
    {
        return true;
    }
}

Answer 1

3是3.5的倍数。5是5.7的倍数。7是7的倍数。您编写的代码对3、5或7的任何倍数都返回false，因此它不可能对这些数字返回true。你只需要检查比你要检查的数小的素数的整除性。

您还可以通过大量不必要的复合数字来检查整除性；例如，一个数字不能是4的倍数而不是2的倍数，也不能是6的倍数而不是2和3的倍数。这些检查只会浪费时间。

最后，从长远来看，你的代码100%都是错的，因为它检查的最高质数是7。它会说169 (13 * 13)是质数，因为它不能被你检查的任何数字整除，但它显然是复合的。对于试除法，您需要检查所有小于或等于floor(sqrt(n))的素数，方法是对组合进行大量不必要的检查，或者在执行过程中建立素数列表(类似于Eratosthenes筛子，通常被CS类型称为筛子，但我不认为严格意义上是等价的)。

Answer 2

一个非常简单(但并不是所有的高效)的方法：

bool is_prime(int i)
{
    int root = (int)std::sqrt(i);
    bool result = true;
    for (int j = 2; j <= root; ++j)
    {
        if (i % j == 0)
        {
            result = false;
            break;
        }
    }
    return result;
}

Answer 3

你可能想看看this的文章。

这是一种系统地寻找质数的方法。使用此算法不断查找质数，直到达到输入的上限值。