编程求区间素数 (求区间素数之和)

想必大家在上学期间我们都编写过寻找某区间的素数，但是怎么能优化我的代码，怎么样能够写出漂亮的代码，这就需要我们来下功夫了。

素数：质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数;否则称为合数。

给出常用的简单的三种方法：遍历法（也可理解为穷举法）、折半法、开根法。

// vs_2.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <stdio.h>
#include "math.h"
//方法1：最简单方法（从2到n-1每个数均整除判断）时间复杂度O(n)
int isPrime0(int k){
		/*判断n是否是素数，是则返回1，不是则返回0*/
	int j;
	for(j=2;j<k/2;j++){
		if(k%j==0) return 0;/*n可以被i整除，因此n不是素数，返回0*/
	}
	return 1;/*n是素数，返回1*/
}
//方法2：遍历到 k/2,就可以了，数学知识
int isPrime1(int k){
		/*判断n是否是素数，是则返回1，不是则返回0*/
	int j;
	if (k <= 1) {
        printf("illegal input!\n");//素数定义
        return -1;
    }
	for(j=2;j<k/2;j++){
		if(k%j==0) return 0;/*n可以被i整除，因此n不是素数，返回0*/
	}
	return 1;/*n是素数，返回1*/
}
//方法3：开根法，数学知识
/*  从2到\sqrt{}n均整除判断，时间复杂度O(\sqrt{}n)
   （原因：素数是因子为1和本身， 如果数c不是素数，则还有其他因子，
	其中的因子，假如为a,b.其中必有一个大于sqrt(c) ，一个小于sqrt(c) 。
	所以m必有一个小于或等于其平方根的因数，
	那么验证素数时就只需要验证到其平方根就可以了。
	即一个合数一定含有小于它平方根的质因子。）
*/
int isPrime2(int k){
	int i;
	if (k <= 1) {
        printf("illegal input!\n");//素数定义
        return -1;
    }
	for(i=2;i<=(int) sqrt((double) k);i++){
		if(k%i==0) return 0;/*n可以被i整除，因此n不是素数，返回0*/
	}
	return 1;/*n是素数，返回1*/
}
void getPrime(int low,int high)
{				/*寻找[low,high]之间的素数*/
    int i;
	if(low > high){
		 printf("error !\n");//素数定义
		 return ;
	}
    for(i=low;i<=high;i++) {
        if(isPrime2(i)) {
            printf("%d ",i);		/*如果i是素数，则打印出来*/
	   }
	}
}

int main(int argc, char* argv[])
{
	int low,high;
    printf("Please input the domain for searching prime\n");
    printf("low limitation:");
    scanf("%d",&low);
    printf("high limitation:");
    scanf("%d",&high);
    printf("The whole primes in this domain are\n");
    getPrime(low,high);
	while(1){
	}
    //getchar();
	return 0;
}

运行结果：执行效率非常的快。

运行结果