解题思路:
明确一个条件,任何合数都能表示成一系列素数的积。
然后利用了每个合数必有一个最小素因子,每个合数仅被它的最小素因子筛去正好一次。
所以为线性时间
参考代码:
#include<stdio.h> int primes(int n); //其中primes()函数是用来排素数的函数 int prime[100000]={0}; //用来存储素数的数组,初始化全部为0 int p[100000]={0}; //用来间接验算是不是素数的数组,初始化全部为0 int main() { int number,i,size; //其中number为用户输入的数,size为prime()传回来的在0~number以内有多少个素数 scanf("%d",&number); size=primes(number); //传回多少个素数 for(i=0;i<size;i++) { printf("%d\n",prime[i]); //输出 } return 0; } int primes(int n) { int top=0,i,j; //定义top为prime[]中已有的素数个数 for(i=2;i<=n;i++) { if(!p[i]) //判断p[i]有没有被修改过,如果没有被修改过,就还是0, // 则对应此时的i为素数,否则就是1,将可以判断其肯定不是素数. { prime[top++]=i; //输入素数 } for(j=0;j<top&&i*prime[j]<=n;j++) { p[i*prime[j]]=1; //这个是欧拉筛选的精髓,当前的值与前面已经出现的素数相乘,其合数肯定不是素数,为其 //赋值1,这样在前面!p[i]判断的时候就可以跳过了 if(i%prime[j]==0) //关键 prime数组 中的素数是递增的,当 i 能整除 prime[j], //那么 i*prime[j+1] 这个合数肯定被 prime[j] 乘以某个数筛掉。 break; // 因为i中含有prime[j], prime[j] 比 prime[j+1] 小。接下去的素数同理。所以不用筛下去了。 } } return top; }
希望对大家有帮助,有bug或者是问题,请在下面评论区留言
0.0分
3 人评分
C二级辅导-同因查找 (C语言代码)浏览:540 |
C语言程序设计教程(第三版)课后习题7.2 (C语言代码)浏览:581 |
简单的a+b (C语言代码)浏览:469 |
C二级辅导-公约公倍 (C语言代码)浏览:1483 |
A+B for Input-Output Practice (C语言代码)浏览:445 |
数组与指针的问题浏览:698 |
C语言程序设计教程(第三版)课后习题10.1 (C语言代码)浏览:512 |
矩阵的对角线之和 (C语言代码)浏览:1274 |
C二级辅导-统计字符 (C语言代码)浏览:616 |
C语言程序设计教程(第三版)课后习题7.4 (C语言代码)浏览:471 |