求100~200间的全部素数

C语言求100~200间全部素数的程序一、基础方法逐个判定1. 非函数方式#includestdio.hintmain(){inti,j,isPrime;printf(100~200之间的素数\n);for(i100;i200;i){isPrime1;if(i1)isPrime0;for(j2;ji;j){if(i%j0){isPrime0;break;}}if(isPrime){printf(%d ,i);}}printf(\n);return0;}2. 函数方式#includestdio.hintisPrime(intn){inti;if(n1)return0;for(i2;in;i){if(n%i0)return0;}return1;}intmain(){inti;printf(100~200之间的素数\n);for(i100;i200;i){if(isPrime(i)){printf(%d ,i);}}printf(\n);return0;}二、优化方法√n优化1. 基础优化#includestdio.h#includemath.hintisPrime(intn){if(n1)return0;inti,sqrtN(int)sqrt(n);for(i2;isqrtN;i){if(n%i0)return0;}return1;}intmain(){inti;printf(100~200之间的素数\n);for(i100;i200;i){if(isPrime(i)){printf(%d ,i);}}printf(\n);return0;}2. 排除偶数#includestdio.h#includemath.hintisPrime(intn){if(n1)return0;if(n2)return1;if(n%20)return0;inti,sqrtN(int)sqrt(n);for(i3;isqrtN;i2){if(n%i0)return0;}return1;}intmain(){inti;printf(100~200之间的素数\n);for(i101;i200;i2){// 只检查奇数if(isPrime(i)){printf(%d ,i);}}printf(\n);return0;}三、6k±1 优化#includestdio.hintisPrime(intn){inti;if(n1)return0;if(n2||n3)return1;if(n%20||n%30)return0;for(i5;i*in;i6){if(n%i0||n%(i2)0)return0;}return1;}intmain(){inti;printf(100~200之间的素数\n);for(i100;i200;i){if(isPrime(i)){printf(%d ,i);}}printf(\n);return0;}四、筛法埃拉托斯特尼筛法#includestdio.h#includestdbool.hvoidsieveOfEratosthenes(intlower,intupper){inti,sizeupper1;bool*isPrime(bool*)malloc(size*sizeof(bool));// 初始化for(i0;iupper;i){isPrime[i]true;}isPrime[0]isPrime[1]false;// 筛选for(i2;i*iupper;i){if(isPrime[i]){for(intji*i;jupper;ji){isPrime[j]false;}}}// 输出指定范围的素数printf(100~200之间的素数\n);for(ilower;iupper;i){if(isPrime[i]){printf(%d ,i);}}printf(\n);free(isPrime);}intmain(){sieveOfEratosthenes(100,200);return0;}五、递归方法#includestdio.hintisPrimeRecursive(intn,inti){if(i1)return1;if(n%i0)return0;returnisPrimeRecursive(n,i-1);}intisPrime(intn){if(n1)return0;returnisPrimeRecursive(n,n/2);}intmain(){inti;printf(100~200之间的素数\n);for(i100;i200;i){if(isPrime(i)){printf(%d ,i);}}printf(\n);return0;}六、位运算优化#includestdio.h#includemath.hintisPrime(intn){if(n1)return0;if(n2)return1;if((n1)0)return0;// 位运算判断偶数if(n%30)return0;inti,sqrtN(int)sqrt(n);for(i5;isqrtN;i6){if(n%i0||n%(i2)0)return0;}return1;}intmain(){inti;printf(100~200之间的素数\n);for(i101;i200;i2){if(isPrime(i)){printf(%d ,i);}}printf(\n);return0;}七、数组存储素数#includestdio.hintmain(){intprimes[100],count0;intisPrime,i,j;printf(100~200之间的素数\n);for(i100;i200;i){isPrime1;if(i1)isPrime0;for(j2;j*ji;j){if(i%j0){isPrime0;break;}}if(isPrime){primes[count]i;}}// 输出结果for(i0;icount;i){printf(%d ,primes[i]);}printf(\n);return0;}八、完整测试程序多种算法对比#includestdio.h#includemath.h#includestdbool.h// 基础方法voidfindPrimesBasic(intlower,intupper){intisPrime,i,j;printf(基础方法\n);for(ilower;iupper;i){isPrime1;if(i1)isPrime0;for(j2;ji;j){if(i%j0){isPrime0;break;}}if(isPrime)printf(%d ,i);}printf(\n);}// √n优化voidfindPrimesSqrt(intlower,intupper){intisPrime,i,j;printf(√n优化\n);for(ilower;iupper;i){isPrime1;if(i1)isPrime0;for(j2;j*ji;j){if(i%j0){isPrime0;break;}}if(isPrime)printf(%d ,i);}printf(\n);}// 6k±1优化voidfindPrimes6k(intlower,intupper){intisPrime,i,j;printf(6k±1优化\n);for(ilower;iupper;i){isPrime1;if(i1)isPrime0;if(i%20||i%30)isPrime0;for(j5;j*ji;j6){if(i%j0||i%(j2)0){isPrime0;break;}}if(isPrime)printf(%d ,i);}printf(\n);}// 筛法voidfindPrimesSieve(intlower,intupper){inti;bool*isPrime(bool*)malloc((upper1)*sizeof(bool));for(i0;iupper;i)isPrime[i]true;isPrime[0]isPrime[1]false;for(i2;i*iupper;i){if(isPrime[i]){for(intji*i;jupper;ji)isPrime[j]false;}}printf(筛法\n);for(ilower;iupper;i){if(isPrime[i])printf(%d ,i);}printf(\n);free(isPrime);}intmain(){intlower100,upper200;printf(100~200之间的素数\n\n);findPrimesBasic(lower,upper);findPrimesSqrt(lower,upper);findPrimes6k(lower,upper);findPrimesSieve(lower,upper);return0;}算法复杂度对比算法时间复杂度空间复杂度适用场景基础方法O(n²)O(1)小范围√n优化O(n√n)O(1)中等范围6k±1优化O(n√n/6)O(1)较大范围筛法O(n log log n)O(n)大范围批量筛选输出结果100~200之间的素数为101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199