尝试检查长整数是否为质数

trying to check if a long integer is prime

提问人:bosh 提问时间:10/17/2023 更新时间:10/17/2023 访问量:74

问:

我正在编写一个程序来检查给定的整数是否为素数。我的程序适用于整数,但是当我将其更改为 long 时,它会返回每个自然数作为非素数。

#include<stdio.h>
 
int check_prime(int);
 
main()
{
   int n, result;
 
   printf("Enter an integer to check whether it is prime or not.\n");
   scanf("%d",&n);
 
   result = check_prime(n);
 
   if ( result == 1 )
      printf("%d is prime.\n", n);
   else
      printf("%d is not prime.\n", n);
 
   return 0;
}
 
int check_prime(int k)
{
   if(k==1){
       return 0;
   }
   int c;
 
   for ( c = 2 ; c <= k - 1 ; c++ )
   { 
      if ( k%c == 0 )
     return 0;
   }
   return 1;
}
c 数学

评论

6赞 001 10/17/2023
但是当我把它改成长您应该显示该代码,而不是工作代码。
0赞 BoP 10/17/2023
那么,您是否将所有用途都更改为 .而且,特别是,您是否也更改了代码?long%d
0赞 Gerhardh 10/17/2023
欢迎来到 SO。 隐式返回类型是前几个世纪中已弃用的功能。您应该习惯于提供适当的函数签名。因为他们是: 或main()mainint main(void)int main(int argc, char*argv[])
0赞 Weather Vane 10/17/2023
一旦你使用了更大的类型,你将需要一个更有效的算法。 将开始,大大减少试验部门(使用正确的类型)。if(k<=1) return 0; if(k==2) return 1; if(k%2==0) return 0; for(c=3; c*c<=k; c+=2)
0赞 chux - Reinstate Monica 10/17/2023
@WeatherVane溢出时是大素数附近。 更好。c*c<=kkLONG_MAXc<=k/c

答:

0赞 chux - Reinstate Monica 10/17/2023 #1

我的程序适用于整数,但是当我将其更改为 long 时,它会返回每个自然数作为非素数。

“我的程序适用于整数”,但不适用于所有整数。
在以下情况下失败。
intcheck_prime(n)n <= 0

Enter an integer to check whether it is prime or not.
0
0 is prime.

修复方式if(k==1){ --> if(k <= 1){

将类型从 转换为 是不够的。代码还必须将说明符从 转换为 。否则会导致未定义行为 (UB)。intlongscanf()"%d""ld"

一个常见的 UB 是结果为零。由于返回错误的答案,因此预计会有许多失败的测试。long n; scanf("%d",&n);ncheck_prime(0)

节省时间。启用所有编译器警告。


for ( c = 2 ; c <= k - 1 ; c++ )对于大型来说非常慢,因为迭代次数高达 O(k) 次。k

用。这迭代了 O(√k) 次。for ( c = 2 ; c <= k/c ; c++ )

评论

0赞 Fe2O3 10/18/2023
由于无需检查偶数:??for ( c = 3 ; c <= k/c ; c += 2 )
1赞 chux - Reinstate Monica 10/18/2023
@Fe2O3 如果存在先验,则“无需检查偶数:”是有道理的。如果不是一些先前的偶数测试,则需要从 2 开始。IAC,它仍然是 O(√k)。当然,还有许多其他优化。if (k%2 == 0) return k==2;for()