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");
}