3528 - 质数统计
一个大于1的自然数，除了1和它本身外，不能被其他自然数整除的数称之为素数（质数）。
现在请你写一个程序，计算在某一范围内的质数的个数。
Input
多组输入数据。
每组数据中，分别包含两个整数x,y(0<=x<=y<=100000)。
Output
对于每组数据，输出在区间[x,y]中所有质数的个数。
Examples
Input
3 8 9 16 4 13
Output
3 2 4
Solution C
#include <stdio.h> #include <math.h> int sum(int x,int y); int zhi(int m); int main () { int x,y; while(scanf("%d %d",&x,&y)!=EOF) { printf("%d\n",sum(x,y)); } return 0; } int sum(int x,int y) { int i;int count=0; for(i=x;i<=y;i++) { if(zhi(i)==1) count++; } return count; } int zhi(int m) { int i; if(m==0||m==1) return 0; else if(m==2) return 1; else if(m%2==0) return 0; else for(i=3;i<=sqrt(m);i+=2) { if(m%i==0) return 0; } return 1; }
Solution C++
#include <iostream> #include <vector> #include <algorithm> #include <string> #include <sstream> #include <cstring> #include <cstdio> #include <cstdlib> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <numeric> #include <cassert> #include <complex> #include <ctime> #define clr(x,a) memset(x,a,sizeof(x)) #define sz(x) (int)x.size() #define rep(i,n) for(int i=0;i<n;i++) #define repeat(i, a, b) for(int i=(a);i<=(b);i++) #define all(v) (v).begin(), (v).end() #define Unique(store) store.resize(unique(store.begin(),store.end())-store.begin()) #define X first #define Y second using namespace std; const int N=1e5+10; bool isp(int n) { for (int i=2;i*i<=n;i++) { if (n%i==0) return false; } return true; } bool v[N]; int main () { memset(v,0,sizeof v); for (int i=2;i<=100000;i++) v[i]=isp(i); int a,b; while (cin>>a>>b) { int ret=0; for (int i=a;i<=b;i++) ret+=v[i]; cout<<ret<<endl; } return 0; }