C语言求素数的方法：试除法和埃拉托斯特尼筛法

🚌 试除法

1. 理论基础

• 素数：是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。
• 任何一个大于1的自然数N，如果N不为质数，那么N可以唯一分解成有限个质数的乘积。

2. 代码实现：求200以内的素数并输出

#include <stdio.h>
#include <math.h>
#include <time.h>
#define N 200

int main(void){
    int prime[N/2] = {2,3,5}; //先预置三个基本的素数
    int j, count = 3;
    clock_t start, finish;
    start = clock();
    //法1：用for循环每个遍历
    // for(int i = 6; i <= N; i++){
    //     if(i%2!=0 && i%3!=0){
    //         for(flag = 1, j = 0; prime[j] <= sqrt(i); j++)
    //             if(i%prime[j] == 0){
    //                 flag = 0;
    //                 break;
    //             }           
    //         if(flag)
    //             prime[count++] = i;
    //     }
    // }

    //法2：用gap跳过2和3的倍数，不用for循环
    int i = 5, gap = 2;
    while(i <= 200){
        i += gap;
        gap = 6 - gap;
        //只需在小于等于根号i的质数里循环
        for(j = 0; prime[j] <= sqrt(i); j++)  //also can: prime[j]*prime[j] <= i, because sqrt(i) may not be precise enough.
            if(i%prime[j] == 0)
                break;        
        if(prime[j] > sqrt(i))  //如果没有执行break，if里条件一定为真
            prime[count++] = i;
    }

    //打印
    printf("Total: %d\n", count);
    for(int i = 0; i < count; i++)
        printf("%d  ", prime[i]);
    finish = clock();
    printf("\nRun time: %ld ms", finish - start);

    return 0;
}

3. 主要技巧

1. 不要处理除2和3外2和3的倍数（通过使用gap变量）
2. 当满足 i<=200且i不是2和3的倍数 后，用小于等于根号i的质数去除，因为任何一个大于1的自然数N，如果N不为质数，那么N可以唯一分解成有限个质数的乘积。

🗻 埃拉托斯特尼筛法

1. 理论基础

• 埃拉托斯特尼筛法（sieve of Eratosthenes）：要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。
• 具体做法：给出要筛数值的范围n，找出以内的素数。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；不断重复下去......

2. 代码实现：求200以内的素数并输出

#include <stdio.h>
#include <time.h>
#define DELETED 1
#define KEPT 0
#define MAX 100

int main(void){
    int sieve[MAX+1] = {KEPT};
    int i, j, prime, count = 1;
    clock_t start, finish;
    start = clock();
    //筛选
    for(i = 0; i <= MAX; i++)
        if(sieve[i] == KEPT){
            prime = 2 * i + 3;
            count++;
            for(j = prime + i; j <= MAX; j += 2*i+3) //删除倍数
                sieve[j] = DELETED;
        }
    //输出
    finish = clock();
    printf("Run time: %ld  Total: %d\n", finish-start, count);
    for(int k = 0; k <= MAX; k++)
        if(sieve[k] == KEPT)
            printf("%d  ", 2*k+3);

    return 0;
}

3. 改进：线性筛法

因为任何一个非质数（合数）都可以分解成质数的连乘积，所以上面的程序很多非质数（除了平方数）是重复删除的，比如有一个数是3717*23，那么在删除3的倍数时会删到它，删除7、17、23的倍数的时候也会删到它，效率自然就不高。线性筛法就是使在删除非质数的时候绝对不做重复的工作，进而提高效率。

关键就是如何安排删除的次序。而容易知道，任何一个合数，都可以写成n=p^k*q的形式，p是因式分解中最小的素数，q >= p。于是当p是素数时，先删除p²、p³...再找出比p大且没有被删除的q，然后删除pq、p²q...直到大于n为止。

#include <stdio.h>
#include <stdlib.h>
#define MAX 1000
//定义类函数宏
#define INITIAL(n) {                      \
    for(unsigned long i = 2; i <= n; i++) \
        previous[i] = i-1, next[i] = i+1; \
    previous[2] = next[n] = 0;         \
}                                          
#define NEXT(x) x = next[x]
#define REMOVE(x) next[previous[x]] = next[x], previous[next[x]] = previous[x]

int main(void){
    unsigned long previous[MAX+1], next[MAX+1];
    unsigned long prime, fact, mult, count = 0, n;
    char line[50], *dummy;
    //获取右范围
    printf("Prime numbers between 2 --> (must be <= %d) ", MAX);
    gets(line);
    n = strtoul(line, &dummy, 10);
    //删除倍数
    INITIAL(n);
    for(prime = 2; prime*prime <= n; NEXT(prime))
        for(fact = prime; prime*fact <= n; NEXT(fact))
            for(mult = prime*fact; mult <= n; mult *= prime)
                REMOVE(mult);
    //打印
    for(int i = 2; i != 0; NEXT(i)){
        printf("%ld  ", i);
        count++;
    }
    printf("\nTotal: %ld", count);

    return 0;
}

20190820