首页 > 代码库 > 学了一种新的素数筛，和以前的不一样哦！
学了一种新的素数筛，和以前的不一样哦！
求素数
Time Limit: 100ms Memory limit: 65536K 有疑问？点这里^_^
题目描述
求小于n的所有素数的数量。
输入
多组输入，输入整数n(n<1000000），以0结束。
输出
输出n以内所有素数的个数。
示例输入
100
示例输出
4
提示
以这道题目为例，要找出n以内的素数， n<=1000000.
为了节省时间，用素数筛 先把1000000以内的素数全部标记出来！
此素数筛核心算法代码：
这样跑完这个代码，是素数的会标记为0， 不是素数的标记为1。 数据处理完毕！
int f[1000004]; int i, j; memset(f, 0, sizeof(f)); f[1]=1 ; //标记1的不是素数 标记0的是素数 i=2; while(i<=500000) { for(j=i*2; j<=1000000; j+=i ) { f[j]=1; } i++; while(f[i]==1) { i++; } }
#include <stdio.h>#include <string.h>int f[1000004];int main(){ int n; int i, j; memset(f, 0, sizeof(f)); f[1]=1 ; //标记不是 i=2; while(i<=500000) { for(j=i*2; j<=1000000; j+=i ) { f[j]=1; } i++; while(f[i]==1) { i++; } } int k, cnt; while(scanf("%d", &n) && n!=0 ) { cnt=0; for(k=1; k<n; k++) { if(f[k]==0) cnt++; } printf("%d\n", cnt ); } return 0;}
学了一种新的素数筛，和以前的不一样哦！
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。