知道为什么这个程序返回 987 是质数（当它不是质数时）吗？

Question

我认为问题出在 for 循环上，但我无法理解。这是学校的作业，我应该只用for循环和if语句来解决！

#include <stdio.h>
int is_prime(int n){
  for (int i=2;i<n;i++){
    if (n%i!=0){
      return 1;
    }
    else{
      return 0;
    };
  };
}

int main(void){
  printf("%d\n", is_prime(11));  // 11 is a prime.      Should print 1.
  printf("%d\n", is_prime(383)); // 383 is a prime.     Should print 1.
  printf("%d\n", is_prime(987)); // 987 is not a prime. Should print 0.
}

Answer 1

首先是 if 语句和 for 循环本身之后的 null 语句

  for (int i=2;i<n;i++){
    if (n%i!=0){
      return 1;
    }
    else{
      return 0;
    };
    ^^^
  };
  ^^^

是多余的。

由于 if 语句，一旦 n % i 不等于 0 或等于 0，for 循环就会被中断。所以一般来说，函数的行为不依赖于传递的数字是否为素数。

如果你将移动 return 语句

return 1;

正如其他人所建议的那样，在循环之外，函数仍然不正确。它将显示 0 和 1 是质数，而它们不是。

循环的条件也使循环效率低下至少因为在进入循环之前很清楚除了2之外的任何偶数都不是素数。

注意函数参数必须是无符号整数类型

函数可以这样定义

#include <stdio.h>

int is_prime( unsigned long long int n )
{
    int prime = n % 2 == 0 ? n == 2 : n != 1;
 
    for ( unsigned long long int i = 3; prime && i <= n / i; i += 2 )
    {
        prime = n % i != 0;
    }

    return prime;
}

int main(void) 
{
    printf( "%d\n", is_prime( 11 ) );
    printf( "%d\n", is_prime( 383 ) );
    printf( "%d\n", is_prime( 987 ) );
  
    return 0;
}

程序输出为

1
1
0

Answer 2

问题出在return 1循环内。当你发现 one i 不是 n 的因数时，你假设 n 是质数。但是你必须保证 all i 不是素数因数，所以 return 1 必须放在之后循环。但是，这会导致 < 2 的数字被视为素数，因为它们根本不进入循环。因此，你还必须在开头额外添加一个if。

顺便说一句：n 的每个除数（除了 n 本身）必须 <= sqrt(n)，因此您可以大大加快函数的速度。

#include <math.h>

int is_prime(int n) {
  if (n < 2)
    return 0;
  int max_divisor = sqrt(n);
  for (int i = 2; i <= max_divisor; i++) {
    if (n % i == 0)
      return 0;
  }
  return 1;
}

Answer 3

问题：return 语句

  return 1;
}
else{
  return 0;

它会导致循环立即退出。在您的情况下，它也会在达到第一个“1”后立即退出。

解决方案：您应该尝试将值存储在变量中，并在循环结束时与“1”或“0”进行比较

知道为什么这个程序返回 987 是质数（当它不是质数时）吗？

Any idea on why this program is returning that 987 is a prime number (when it is not a prime number)?

c

for-loop

if-statement

primes

function-definition