判断素数的几种方法

下面是我自己的四种判断素数的方法^^可能有点烂，凑合得看吧O(∩∩)O哈哈~
第一种
直接判断（暴力）（因此判断一个整数m是否是素数，只需把m被 2 ~ m-1 之间的每一个整数去除，如果都不能被整除，那么m就是一个素数。）

int is_Prime(int n) {
    int i;
    if(n < 0) {
        return 0;
    }

    if(n == 1 || n == 0) {
        return 0;
    } else if(n == 2) {
        return 1;
    }

    for(i = 2;i < n;i++) {
        if(!(n % i)) {
            break;
        }
    }
    if(i == n) {
        return 1;
    } else {
        return 0;
    }
}

第二种
对第一种方法的优化（m不必被 2 ~ m-1 之间的每一个整数去除，只需被 2 ~ 之间的每一个整数去除就可以了。如果m不能被 2 ~ 间任一整数整除，m必定是素数。例如判别17是是否为素数，只需使17被2~4之间的每一个整数去除，由于都不能整除，可以判定17是素数。）

int is_Prime(int n) {
    int i;
    int k;

    if(n <= 0 || n == 1) {
        return 0;
    }

    if(n == 2) {
        return 1;
    }

    k = (int)sqrt((double)n);
    for(i = 2;i <= k;i++) {
        if(!(n%i)) {
            break;
        }
    }
    if(i >  k) {
        return 1;
    } else {
        return 0;
    }

}

在这里关于sqrt()函数，在math.h库里面，包含math.h库时，编译时最后需要加-lm

第三种
一般的线性筛法 （初始时，假设全部都是素数，当找到一个素数时，显然这个素数乘上另外一个数之后都是合数，把这些合数都筛掉）

void get_prime(int n) {
    int i;  
    int j;  
    for(i = 2;i < n;i++) {
        a[i] = 1; 
    }
    for(i = 2;i <= sqrt(n);i++) {
        if(a[i] == 1) {
            for(j = i*2;j < n;j += i){
                    a[j] = 0;  
            }  
        }  
    }  
}  

第四种
快速线性筛法 （原理：1.一个合数是由n个素数的乘积所组成的 2.素数的倍数不是素数。）
（我们知道合数可以由一个质数数与另一个数相乘得到
而同时假设合数a=质数b×质数c×一个数d
令e=c × d,假设b ≥ e,e为合数,令f=d × b
a=f × c ,其中c
即比一个合数数大的质数和该合数的乘积可用一个更大的合数和比其小的质数相乘得到
这也是if(!( i % prime[j]))break;的含义,这也是线性筛法算质数表的关键所在）

const int Max = 2000000;
long long prime[Max] = {0};

int k = 0;
int a[Max] = {1,1};

void init() {
    long long i;
    long long j;
    for(i = 2;i < Max;i++) {
        if(!a[i])
        prime[k++] = i;

        for(j = 0;j < k && i * prime[j] < Max;j++) {
            a[i*prime[j]] = 1;

            if(i%prime[j] == 0)
                break;
        }
    }
}

第五种/(ㄒoㄒ)/~~
实际我也不会，不过在codevs上看到一个题/(ㄒoㄒ)/~~前面的方法都不对
链接