0

我在处理这个 C++ 代码时遇到了问题。整数num是一个我想检查它是否是素数的数字。然而这个程序总是返回假。这可能很简单，但我找不到任何东西。

for(int i=2;i<num;i++){ //primes are allowed to be divided by 1 so we start at 2
        if(num % i == 0){ //can be divided by a number other than itself or 1 so we trip out
            return false;
        } else if(i == num){ //if we've already done checks as high as possible and not tripped out yet then report success
            return true;
        }
}
4

6 回答 6

7

i == num永远不会发生，因为您的循环条件是i<num. 尝试：

for(int i=2;i<num;i++){ //primes are allowed to be divided by 1 so we start at 2
    if(num % i == 0){ //can be divided by a number other than itself or 1 so we trip out
        return false;
    } else if(i == num-1){ //if we've already done checks as high as possible and not tripped out yet then report success
        return true;
    }
}

如下所述，else这里的条件是多余的，你只需要从 2 到sqrt(num)- 进行检查，因为其余的因素已经检查过了。

根据您想要解决问题的复杂程度，可以进行更多改进。现实中的大多数方法都使用概率算法。

于 2012-08-01T06:42:24.480 回答
4

您不必检查每个数字，因为其中很多很容易被排除。例如，在检查num不能被 整除之后2，您可以跳过所有其他偶数。这可以为您节省一半的测试。

我们也绝对知道任何其他因素必须小于num/2（或真的sqrt(num)，但这更难计算）。这些知识可以为我们节省另一半的测试。

所以现在我们有：

if (num % 2 == 0)
    return false;

for(int i = 3; i < num / 2; i += 2){ 
     if(num % i == 0){ //can be divided by a number other than itself or 1 so we trip out
         return false;
     }
}

// arriving here we have found no factors, so it must be a prime
return true;
于 2012-08-01T07:31:42.500 回答
1 
bool CheckPrime(int num) {
    bool yayornay = true;
    for(int i = 2; i < num; i++) {
         if(num % i == 0) {
             yayornay = false;
             break;
         }
    }
    return yayornay;
}
于 2012-08-01T07:57:13.597 回答
1

对Will Ness 的代码做了一个小优化，只计算for 外数的sqrt。条件检查执行多次，每次计算sqrt都没有意义。

if( num == 2 ) return true;
if( num < 2 || num % 2 == 0 ) return false;
int sqrt = sqrt(num);

for( int i=3; i<=sqrt; i+=2 ){   
        if(num % i == 0){ 
            return false;
        } 
}
return true;

到目前为止，我认为这是最有效的方法！

于 2012-08-01T11:38:43.393 回答
0

这是写下您的意思的正确方法：

int i=2;                     // move declaration out
for(/*int i=2*/;i<num;i++){ 
        if(num % i == 0){ 
            return false;
        } // else            // and the final test too
}
if(i == num){                
    return true;
}

但这不是有效的。您只需检查i' 不超过sqrt(num). 另外，如果您检查num%2，则不再需要检查任何其他偶数，因此您可以使用 2 的增量。或者您甚至可以按6计数：

if( num == 2 || num == 3 ) return true;
if( num < 2 || num % 2 == 0 || num % 3 == 0 ) return false;
for( int i=5, j=7, lim=sqrt(num); i<=lim; i+=6, j+=6 ){   
        if( num % i == 0 || num % j == 0 ){ 
            return false;
        } 
}
return true;

（注意：这比这里的另一个答案更有效，它说这是这个答案的初始版本的“优化”）。

于 2012-08-01T11:26:38.540 回答
0 
bool isprime(int n)
{
    if(n<2) return false;
    if(n==2)return true;
    for(int i=2;i<=sqrt(n);i++)
        if(n%i==0) return false;
    return true;
}
于 2014-10-25T13:38:44.947 回答