首页 > 代码库 > ZZUOJ-1222- 属于ACMer的游戏 猜素数 （某月赛，总结一下素数筛选法）
ZZUOJ-1222- 属于ACMer的游戏 猜素数 （某月赛，总结一下素数筛选法）
题目位置：1222: 属于ACMer的游戏 猜素数
1222: 属于ACMer的游戏 猜素数
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 88 Solved: 21
[Submit][Status][Web Board]
Description
ACM实验室的众大神们喜欢聚餐大家一起HAPPY 尤其卢学长喜欢请大家HAPPY,但是卢学长请吃饭有一个习惯，大家要一起玩一个热身游戏,猜素数.
游戏规则如下：
正常人的版本是这样：比如卢学长先约定一个数，并约定一个范围比如1~1000，然后大家开始猜范围内的数，逐渐缩小范围，比如唐学长是卢学长的下一个位置的人，然后唐学长猜了550，如果和卢学长约定的数一样则唐学长接受惩罚，否则缩小范围如果约定的数大于550则范围变成550~1000，否则变成1~550.同理挨个猜数，直到有人接受惩罚。
但是ACM实验室的众大神的版本作了一点点改进，即事先约定的数和后面猜的数必须是素数 这可难为了冷神，冷神不知道一共会有多少素数。所以只能拜托机智的众学弟学妹了。
输入两个数a,b（1<=a,b<=10^7）判断a,b范围内(包括a,b)会有多少素数呢？
数据不保证a小于b。
Input
a,b两个数（1<=a,b<=10^7）
Output
t 表示范围内有多少个素数
Sample Input
1 1015 202 300
Sample Output
4262
HINT
Source
geek eric
这里来总结一下素数筛选法。。（针对这题）
题意：很简单，就是去找两个数的之间的素数的个数（包括这两个数，且两个数的大小顺序不固定）
一般的线性筛法AC代码（Memory：40624 Time：640）：
/*************************************************************************
> File Name: a.cpp
> Author: zzuspy
> Mail: zzuspy@qq.com
> Created Time: 2014年12月01日 星期一 12时50分31秒
************************************************************************/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<stack>
#include<queue>
using namespace std;
const int maxn = 10000005;
int vis[maxn] = {1,1};
int main()
{
int m = sqrt(maxn+0.5);
for(int i = 2; i<=m; i++)
if(!vis[i])
{
for(int j = i*i; j<=maxn; j+=i) vis[j] = 1;//筛法过程
}
int a, b;
while(scanf("%d %d", &a, &b)!=EOF)
{
int ans = 0;
int t = max(a,b);
a=min(a,b);
b=t;
for(int i=a; i<=b; i++)
{
if(!vis[i])ans++;
}
printf("%d\n", ans);
}
return 0;
}更快的线性筛法AC代码（Memory：21092 Time：296）（时间是省了一半多，但是却复杂了一倍多，按情况选择更好的方法吧）：
/*************************************************************************
> File Name: b.cpp
> Author: zzuspy
> Mail: zzuspy@qq.com
> Created Time: 2014年12月01日 星期一 13时44分39秒
************************************************************************/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<stack>
#include<queue>
using namespace std;
const int maxn = 10000005/2;
int vis[maxn];
int main()
{
int m = (int) sqrt(maxn);
for(int i = 0; i<m; i++)
if(!vis[i])//如果 i+i+3 是素数
{
for(int k=i+i+3, j=k*i+k+i; j<maxn; j+=k)
{//这里只筛选奇数
// 筛法起点是 p[i]所对应素数的平方 k^2 // k^2在 p 中的位置是 k*i+k+i // 下标 i k*i+k+i //对应数值 k=i+i+3 k^2 vis[j] = 1;
}
}
int a, b;
while(scanf("%d %d", &a, &b)!=EOF)
{
int t = max(a,b), ans=0;
a=min(a,b); b=t;
if(a<=2)
{
ans++;
a=2;
}
if(b>=3 && b-a>=1)
for(int i=a/2-1; i<=(b-3)/2; i++)
{
if(!vis[i])ans++;
}
else if(b==a && a%2==1 && !vis[(a-3)/2])ans++;
printf("%d\n", ans);
}
return 0;
}//素数都存放在 p 数组中，p[i]=true代表 i+i+2 是素数。//举例，3是素数，按3*3,3*5,3*7...的次序筛选，因为只保存奇数，所以不用删3*4，3*6....ZZUOJ-1222- 属于ACMer的游戏 猜素数 （某月赛，总结一下素数筛选法）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。