素数生成算法-C语言版 2020-09-06 方法一: 1234567891011121314151617181920212223242526272829303132333435363738#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;} 方法二: 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include<stdio.h>#define PRIME_UPPER_BOUND 1000000 //素数上界,生成小于该值的所有素数int is_prime[PRIME_UPPER_BOUND];//将所有素数初始为0int 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;} 赏 谢谢你请我吃糖果 扫一扫,分享到微信