我们一般写的埃氏筛消耗的时间都是欧拉筛的三倍,但是欧拉筛并不好想(对于我这种蒟蒻)
虽然 -- 我 -- 也可以背过模板,但是写个不会的欧拉筛不如写个简单易懂的埃氏筛
于是就有了优化
这个优化还是比较厉害的,能把埃氏筛的消耗的时间提的跟欧拉筛差不多
以下内容需要先学会埃氏筛
学会的埃氏筛就明白它的原理了吧
#include<bits/stdc++.h>
using namespace std;
int n, m ,Is_p[10000001];
int main() {
cin >> n >> m;
Is_p[1] = 1;
for(int i = 2; i <= n; ++i)
if(Is_p[i] == 0)
for(int j = 2; i * j <= n; ++j)
Is_p[i * j] = 1;
int a = 0;
for(int i = 1; i <= m ;++i) {
scanf("%d", &a);
if(Is_p[a] == 1) cout << "No
";
else cout << "Yes
";
}
return 0;
}
这是一种最普通的埃氏筛了
由于我的小号名字很嚣张,我就抹掉了
运行总时间是4000多ms
炒鸡慢啊,有木有
在这份代码中有一个地方明显可以优化
for(int i = 2; i <= n; ++i)
if(Is_p[i] == 0)
// for(int j = 2; i * j <= n; ++j)
Is_p[i * j] = 1;
1.
绿油油的那行就是,i * j <= n,这个语句中每次执行循环都会执行一遍
i * j执行多了也会卡的,所以不如定义一个数(yy) = n / i , j只需要枚举到yy就可以.
2.
还有最外层循环的i <= n,其实没必要执行这么多次,因为一个数n总能被
√n 筛掉所以只需要枚举到√n.
但是sqrt(n)算多了反而得不偿失,所以像刚才一样处理
3.
还有一个更重要的地方,也是每一个课本上都讲过的,j只需要从i开始,为什么课本上都有.
完成这3项,埃氏筛也基本不能更快了,
交上去试试:
我同学的欧拉筛(这是位dalao,没事可以加他去膜一膜,他有多么强呢?他跟我学的时间差不多,我才刚学树,他就已经会了主席树......)
可以看到10个点总共慢了200ms,平均一个才慢20ms.
估计没有出题人可以把时间卡的这么"好"(让欧拉筛过,但不让埃氏筛过)吧
而且我占的空间比他少的多
我来顺便分析一下他的名字,其实他的名字后两个字是带三点水的但是去掉了,并且在前面加上了个水比
这说明了什么,他想说明他"没有水",但是说自己很水,
用人话来讲就是:不水而且很谦虚
上述内容纯属扯淡,进入正题
emmmm..好像没什么要说的了
交代
.-' _..`.
/ .'_.'.'
| .' (.)`.
;' ,_ `.
.--.__________.' ; `.;-'
| ./ /
| | /
`..'`-._ _____, ..'
/ | | | |
/ /| | | |
/ / | | | |
/_/ |_| |_| \_
|__ |__ |__ |__
#include<bits/stdc++.h>
using namespace std;
bool a[10000001];
void ol(int x){
int xx = sqrt(x);
for (int i = 2; i <= xx; ++i)
{
if (a[i] == 0)
{
int yy = x / i;
for (int j = i; j <= yy; ++j)
{
a[i * j] = 1;
}
}
}
}
int main()
{
int n,m,t;
cin>>n>>m;
a[0] = 1;//这里要特判一下,不然会WA两个点
a[1] = 1;
ol(n);
for(int i=1;i<=m;i++){
scanf("%d",&t);
if(a[t] == 0)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}
我把欧拉筛也贴上吧
#include<cstdio>
#include<iostream>
using namespace std;
int n, m, p[10000001], cnt, IsNotPrime[10000001];
int main() {
scanf("%d%d", &n, &m);
IsNotPrime[0] = IsNotPrime[1] = 1;
for(int i=2; i < n; ++i) {
if(!IsNotPrime[i]) p[++cnt] = i;
for(int j = 1; i*p[j] <= n && j <= cnt; ++j) {
IsNotPrime[i * p[j]] = 1;
if(! (i % p[j])) break;
}
}
int k;
for(int i = 1; i <= m; ++i) {
scanf("%d", &k);
if(IsNotPrime[k]) cout << "No
";
else cout << "Yes
";
}
return 0;
}