0

我需要创建一个在两个输入数字之间生成素数的函数。我通过测试范围内每个数字的素数来做到这一点。问题是数字 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;
    }
}
4

5 回答 5

3

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

您还检查了许多不必要的合数的可分性；例如，一个数字不能是 4 的倍数而不是 2 的倍数，它也不能是 6 的倍数而不是 2和3 的倍数。这些检查除了浪费时间之外没有任何作用。

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

于 2013-10-09T00:09:08.167 回答
1

一个非常简单（但不是那么有效）的方法：

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;
}
于 2013-10-09T00:09:03.373 回答
0

你可能想看看这篇文章。

这是一种寻找素数的系统方法。使用此算法继续查找素数，直到达到输入的上限值。

于 2013-10-09T00:11:38.980 回答
0

看这行代码：

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;

想想如果你插入 2、3、5 或 7 会发生什么。在每种情况下，你会发现数字 mod 2、mod 3、mod 5 或 mod 7 确实为零，所以你的代码将返回错误的。这可能解释了为什么你得到的这些数字不算作素数。

但现在看下一条语句：

else if ((number/1==number) && (number/number==1)){
    return true;
}

在什么情况下这是错误的？每个数字除以一就是它本身，每个数字除以它本身就是一，所以每个数字都通过了这个测试。因此，只要它不能被 2、3、4、5、6、7、8 或 9 整除，您的代码将对任何数字返回 true。尝试插入 11 x 13 = 143。这个数字不是t prime，但你的函数会说它是。

其他人已经发布了您可以采取的其他途径来解决问题，但从根本上说，我认为问题在于，如果除 1 之外没有其他数字并且它本身是除数，则该数字是素数。您的函数将需要以某种方式考虑这一点，可能通过检查它下面的所有不是一个或本身的数字。正如一些答案所建议的那样，可以进一步优化这一点，但您应该知道，在基本层面上，这是需要做的。

希望这可以帮助！

于 2013-10-09T00:19:27.080 回答
0

或者你可以使用这个算法：

#include<iostream>
#include<string>
#include<cmath>

using namespace std;

int main()
{
    int num;
    int count = 0;

    cout << "Enter your range: ";
    cin >> num;

    for(int i = 1; i <= num; i++)
    {
        count = 0;
        for(int j = 2; j <= sqrt(i); j++)
        {
            if(i % j == 0)
            {
                count++;
                break;
            }
        }
        if(count == 0 && i != 1)
            cout << i << "   ";
    }
    cout << endl;   
}
于 2013-10-09T01:05:53.230 回答