提问人:bosh 提问时间:10/17/2023 更新时间:10/17/2023 访问量:74
尝试检查长整数是否为质数
trying to check if a long integer is prime
问:
我正在编写一个程序来检查给定的整数是否为素数。我的程序适用于整数,但是当我将其更改为 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;
}
答:
0赞
chux - Reinstate Monica
10/17/2023
#1
我的程序适用于整数,但是当我将其更改为 long 时,它会返回每个自然数作为非素数。
“我的程序适用于整数”,但不适用于所有整数。
在以下情况下失败。int
check_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)。int
long
scanf()
"%d"
"ld"
一个常见的 UB 是结果为零。由于返回错误的答案,因此预计会有许多失败的测试。long n; scanf("%d",&n);
n
check_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()
评论
long
%d
main()
main
int main(void)
int main(int argc, char*argv[])
if(k<=1) return 0; if(k==2) return 1; if(k%2==0) return 0; for(c=3; c*c<=k; c+=2)
c*c<=k
k
LONG_MAX
c<=k/c