素数生成算法_C语言版@FDDLC

方法一：

#include

#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("%dn",prime[prime_index]);

return 0;

}

方法二：

#include

#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("%dn",prime[prime_index]);

printf("prime_sum: %dn",prime_sum);

return 0;

}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!