欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

C语言判断素数

程序员文章站 2024-01-14 17:35:52
...

题目:编写函数,输入一个正整数n,如果它是素数,输出yes,否则输出NO。

根据定义,被1和它自身整除的、大于1的整数称为素数。

C语言代码:

第一种:n为1或者n太大不适用

#include<stdio.h>
#include<math.h>
int is_prime(int n)
{
	{ 
		for(int i = 2; i*i <= n; i++)
			if(n % i == 0)
				return 0;
           return 1;
	}
}
int main()
{
	int n,len;
	scanf("%d",&n);
    len=is_prime(n);
	if(len)
		printf("yes\n");
	else
		printf("NO\n");
	return 0;
}

解释:
1.n=1会被错误地判断为素数(因为确实没有其他因子)
2.n太大ii可能溢出,如果n是一个接近int的最大值的素数,则当循环到i=46340 时,ii=2147395600<n;但i=46341时,i*i=2147488281,超过了int的最大值,溢出变成负 数

第二种通用版:

#include<stdio.h>
#include<math.h>
int is_prime(int n)
{
	int i;
	float m;
	if(n==1)
		return 0;
	m=floor(sqrt(n)+0.5);
	for(i=2;i<=m;i++)
		if(n%i==0)
			return 0;
		return 1;
}
int main()
{
	int n,len;
	scanf("%d",&n);
    len=is_prime(n);
	if(len)
		printf("yes\n");
	else
		printf("NO\n");
	return 0;
}

思考:小技巧 ,只需判断小于srqt(n)的整数即可