素数生成算法-C语言版

2020-09-06

方法一：

#include<stdio.h>
#define PRIME_SUM 10 //素数总数

int prime[PRIME_SUM] = {2, 3}; //先把2和3放到prime数组中
int prime_count = 2; //素数计数，目前已有2和3两个素数

void generate_prime()
{
    for(int number = 5; number < 100000000; number = number + 2) //对从5开始的每个奇数进行判断
    {
        int is_prime = 1;

        //当number = 53时，会用3、5、7去除
        //当number = 65时，会用3和5去除，用5除时不行
        for(int prime_index = 1; prime[prime_index] * prime[prime_index] <= number; prime_index++)
        {
            if(number % prime[prime_index] == 0) //若number能被当前素数整除，则number非素数
            {
                is_prime = 0;
                break;
            }
        }

        if(is_prime)
            prime[prime_count++] = number; //number通过考验，欢迎加入素数大家庭~

        if(prime_count == PRIME_SUM) //已经生成PRIME_SUM个素数，收工~
            break;
    }
}
int main()
{
    generate_prime();
    for(int prime_index = 0; prime_index < PRIME_SUM; prime_index++)
        printf("%d\n", prime[prime_index]);

    return 0;
}

点击并拖拽以移动

方法二：

#include<stdio.h>
#define PRIME_UPPER_BOUND 1000000 //素数上界，生成小于该值的所有素数


int is_prime[PRIME_UPPER_BOUND];

//将所有素数初始为0
int prime[PRIME_UPPER_BOUND] = {0};

int generate_prime()
{
    //将所有元素初始化为1，即先假定所有数都为素数。如is_prime[5] = 1, 表示5为素数
    for(int index = 0; index < PRIME_UPPER_BOUND; index++)
        is_prime[index] = 1;

    int prime_count = 0; //用来计算素数个数
    //divisor：除数，起到筛子的作用
    for(int divisor = 2; divisor * divisor <= PRIME_UPPER_BOUND; divisor++)
    {
        //若divisor为素数，则把所有的倍数(自身除外)淘汰。比如divisor = 3是素数，
        //则把6、9、12等数给淘汰
        if(is_prime[divisor]) //4被2筛除过，无须作筛子；9被3筛除过，无须作筛子
        {
            int n_divisor = divisor + divisor;
            while(n_divisor <= PRIME_UPPER_BOUND)
            {
                is_prime[n_divisor] = 0; //将divisor的倍数(自身除外)判为非素数
                n_divisor = n_divisor + divisor; //下一个倍数
            }
        }
    }

    for(int number = 2; number <= PRIME_UPPER_BOUND; number++)
    {
        if(is_prime[number]) //若number是素数，则将其加入到素数大家庭
            prime[prime_count++] = number;

    }

    return prime_count;

}
int main()
{
    int prime_sum = generate_prime();

    for(int prime_index = 0; prime_index < prime_sum; prime_index++)
        printf("%d\n", prime[prime_index]);

    printf("prime_sum: %d\n", prime_sum);

    return 0;
}

点击并拖拽以移动