赞
踩
完善程序:
筛选法求1到N之间有多少质数。
#include <bits/stdc++.h> using namespace std; int N, ANS; int a[1000010]; int main() { freopen("1452.in","r",stdin); freopen("1452.out","w",stdout); cin >> N; int ct=0; //记录被删除的个数 for (int i=2; i*i < N+1; i++) if (a[i]==0) //"选"出质数i { for (int j=i+i; j < N+1; _____ ) { if( ______ ) ct++; a[j]=i; //"筛"掉i的倍数 } } ANS = _______; cout << ANS << endl; return 0; }
第一行1个正整数:N,范围在[1,1000000]。
一个整数。
输入:
100
输出:
25
我的代码:
- #include<bits/stdc++.h>
- using namespace std;
- int a[1000009],n,ans;
- int main()
- {
- cin>>n;
- for(int i=2;;i++)
- {
- if(i>1000000)break;
- if(a[i]==0)
- {
- for(int j=2;;j++)
- {
- if(i*j>1000000)break;
- a[i*j]=1;
- }
- }
- }
- for(int i=2;i<=n;i++) if(a[i]==0)ans++;
- cout<<ans;
- return 0;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。