求素数的算法

素数：大于1的自然数中，只能被1和它本身整除的数。

#include<stdio.h>
#include<time.h>
#include<math.h>
int IsPrime(int n){
    int i;
    if(n%2==0) return 0;//如果n是偶数
    //从3开始 因为2是素数 
    //用sqrt  到√n时就把2到n-1都判断过了
    for(i = 3;i <= sqrt(n);i+=2){//i = i + 2 也是排除偶数
        if(n%i==0) return 0;
    }
    return 1; 
}
int main(){
    int n,i;
    int t1 = clock();
    printf(" 2 "); 
    for(i = 3;i<=100000;i++){
        if(IsPrime(i)) printf(" %d ",i);
    }
    int t2 = clock();
    printf("\n运行时间：%d\n",t2-t1);
}