18
2019
11

C语言判断素数

素数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数。

思路:设m为要判断的数,m 不必被 2 ~ m-1 之间的每一个整数去除,只需被 2 ~  之间的每一个整数去除就可以了。如果 m 不能被 2 ~  间任一整数整除,m 必定是素数。

例如判别 17 是是否为素数,只需使 17 被 2~4 之间的每一个整数去除,由于都不能整除,可以判定 17 是素数。

原因:因为如果 m 能被 2 ~ m-1 之间任一整数整除,其二个因子必定有一个小于或等于 ,另一个大于或等于 。例如 16 能被 2、4、8 整除,16=2*8,2 小于 4,8 大于 4,16=4*4,4=√16,因此只需判定在 2~4 之间有无因子即可。

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int main(){
	int m,k,i;
	printf("请输入一个正整数:");
	scanf("%d",&m);
	if(m <= 1){
		printf("不是素数也不是合数!\n");
		exit(1);	// 退出程序,需注意的是此处不能用break 
	}
	k = sqrt(m);	// k是m的平方根 
	for(i=2; i<=k; i++){
		if(m % i == 0)
		break;
	}
	// 注意最后一次循环,会执行i++,此时 i=k+1,所以有i>k
	if(i > k)
		printf("是素数!\n");
	else
		printf("不是素数!\n");
}


« 上一篇 下一篇 »

返回顶部
请先 登录 再评论,若不是会员请先 注册