判断一个正整数是否为素数(也称作质数)

所谓“素数”,就是只能被自身和1整除的正整数,也称作“质数”。它的对立面是“合数”,合数不仅可以被自身和1整除,还可以被其他正整数整除。
通过分析我们可以得知,一个正整数的整除因子因该是大于等于0、小于等于自身的正整数。所以,就有了一个办法判断一个正整数是否为素数——用[2,N-1]中的正整数(x)整除N,如果有值可以整除N,则N就不是素数。(可以用玉漱是否为0来判断:N % x == 0)
当然还有个优化的方法,可以节省不少计算——就是把除数范围缩减到[2,(int)sqrt(N)],(int)sqrt(N)为对N开方后的值取整数。——因为18能被3整除和18能被6整除其实是一个效果的!下面的源代码就是使用了这种方法:

//判断一个正整数是否为素数(也称作质数)
#include<stdio.h>
#include<math.h>//引用系统的数学函数库

/**判断是否为素数的函数
*如果是素数返回1,否则返回0
**/
int is_primeNum(int num){
	int i,sqrt_num;
	int is_su = 1;

	sqrt_num = (int)sqrt(num);
	for(i = 2;i <= sqrt_num;i++){
		if(num % i == 0){
			is_su = 0;
			break;
		}
	}

	return is_su;
}

void main(){
	int num;
	int is_su;

	printf("please input a number!nsum = ");
	scanf("%d",&num);

	is_su = is_primeNum(num);

	if(is_su == 1){
		printf("%d is a prime number!n",num);
	}else{
		printf("%d is not a prime number!n",num);
	}

}

在这特别声明下:再好的编程技术未必能做出最优秀的软件产品,再优秀的软件产品未必能有良好的市场并被大众认可。所以,设计架构和编程时,要多为用户着想、为同事着想。软件产品再“高端大气上档次”,也是要归结到“人”这个根本性问题上来。所以,良好的软件产品要有不错的可读性和用户体验!
 
 
 

© 2013 – 2015, 李德涛博客. 版权所有.

发表评论

电子邮件地址不会被公开。 必填项已用*标注