正文

[洛谷p3383]线性筛素数-欧拉筛法

nishikino-curtis  nishikino-curtis  2022-10-15  291

关键词：

Description

如题，给定一个范围N，你需要处理M个某数字是否为质数的询问（每个数字均在范围1-N内）

Input&Output

Input

第一行包含两个正整数N、M，分别表示查询的范围和查询的个数。
接下来M行每行包含一个不小于1且不大于N的整数，即询问该数是否为质数。

Output
输出包含M行，每行为Yes或No，即依次为每一个询问的结果。

Solution

代码如下:

#include<iostream>
#include<cstring>
using namespace std;
int num[100000];
long long prime[5000001];
bool is_prime[10000001];
int N,M;
int cnt=1;
int main()
{
for(int k=0;k<10000001;k++)
{
    is_prime[k]=true;
}
cin>>N>>M;
is_prime[0]=false;
is_prime[1]=false;
is_prime[2]=true;
prime[1]=2;
for(int i=2;i<N;i++)
{
   if(is_prime[i]==true){prime[cnt]=i;cnt++;} 
   for(long long j=1;j<=cnt&&prime[j]*i<=N;j++)
   {
       is_prime[prime[j]*i]=false;
       if(i%prime[j]==0)break;
   }
}
for(int i=0;i<M;i++)
{
    cin>>num[i];
    if(is_prime[num[i]]==false)cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
}
return 0;
}

线性筛素数-欧拉筛法

1#include<iostream>2#include<cstring>3usingnamespacestd;4intnum[100000];5longlongprime[5000001];6boolis_prime[10000001];7intN,M;8intcnt=1;9intmain()10{11for(intk=0;k<10000001;k++)12{13i 查看详情

线性筛洛谷p3383线性筛模板

思路：如果我们要筛出[1,n]内的所有素数，使用[1,√n]内的素数去筛就可以了设bool型数组a，a[i]表示i是否被某个素数筛过从2开始枚举每个数i：若a[i]=false，表示i没有更小的素因子，从而知道i是素数。枚举i的所有倍数j，令a[j]=1这... 查看详情

洛谷p3383模板线性筛素数

P3383【模板】线性筛素数题目描述如题，给定一个范围N，你需要处理M个某数字是否为质数的询问（每个数字均在范围1-N内）输入输出格式输入格式：第一行包含两个正整数N、M，分别表示查询的范围和查询的个数。接下来M... 查看详情

线性筛法（欧拉筛法）求素数

时间复杂度O(n)当n比较大时欧拉筛法所用的时间比O(nloglogn)的算法的时间少的会越来越明显为什么呢?因为在欧拉筛法中，每一个合数只被访问并将其所对的f[]的值修改了一次。for(i=2;i<=n;i++){if(f[i]==0){p[++cnt]=i;}for(j=1;j<=cnt;j++){if... 查看详情

数学基础素数线性筛法--欧拉筛法模板普通筛法的优化

质数（素数）：指大于1的所有自然数中，除了1和自身，不能被其它自然数整除的数合数：比1大，但不是素数的数称为合数，合数除了被1和自身整除，还能被其它数整除质因数（素因数或质因子）：能整除给定正整数的质数，... 查看详情

洛谷p3383模板线性筛素数

题目链接：https://www.luogu.org/problem/show?pid=3383题目描述如题，给定一个范围N，你需要处理M个某数字是否为质数的询问（每个数字均在范围1-N内）输入输出格式输入格式：第一行包含两个正整数N、M，分别表示查询的范围和查询的... 查看详情

p3383模板线性筛素数洛谷

https://www.luogu.org/problem/show?pid=3383#sub题目描述如题，给定一个范围N，你需要处理M个某数字是否为质数的询问（每个数字均在范围1-N内）输入输出格式输入格式：第一行包含两个正整数N、M，分别表示查询的范围和查询的个数... 查看详情

洛谷p3383模板线性筛素数

题目描述如题，给定一个范围N，你需要处理M个某数字是否为质数的询问（每个数字均在范围1-N内）输入输出格式输入格式：第一行包含两个正整数N、M，分别表示查询的范围和查询的个数。接下来M行每行包含一个不小于1且... 查看详情

洛谷p3383模板线性筛素数

p3383模板线性筛素数(代码片段)

P3383【模板】线性筛素数欧拉筛O(n)#include<iostream>#include<cstdio>usingnamespacestd;intn,m,cnt,prime[10000002],v[10000002];//prime:素数表v:存某数的最小质因数intmain()scanf("%d%d",&n,&m);for(inti=2;i< 查看详情

[模板]线性筛素数(欧拉筛法)(代码片段)

用途$O(n)$处理出n以内所有素数原理使用合数=最大因数(除1和本身外)*最小质因数的原理来筛，每个数只会被筛一次对于每个数i，令它是某数的最大因数，然后从小到大地找<=i的素数j，则i*j是合数直到找到某个j使得$i\%j==0$，因... 查看详情

欧拉筛（线性筛）

素数筛，就是按照顺序把合数踢掉，剩下的是素数。欧拉筛是一种O（n）求素数的筛法。他避免了埃拉特斯特尼筛法对同一数的多次筛除。欧拉筛的原理是只通过数的最小质因数筛数。先上代码：#include<cstdio>usingnamespacestd;con... 查看详情

洛谷p3383模板线性筛素数(miller_rabin)

素数筛法

...面是埃氏筛先补一个很有意思的东西1+1/2+1/3+1/4+....+1/n=logn线性筛代码欧拉函数对于大范围内求质因数个数硬解肯定太慢，用线性筛优化先用线性筛找到每一个数的最小质因子(rec[i]) 分析：第二个if里，... 查看详情

线性筛

在这里提供三种线性筛的讲解,它们分别是:素数筛,欧拉筛和莫比乌斯筛。 ·筛法正确性的重要理论依据：上述函数均为积性函数。积性函数的性质为:若f(x)是一个积性函数,那么对于任意素数a,b,满足f(ab)=f(a)*f(b) ·一些可爱... 查看详情

洛谷p2640神秘磁石（欧拉筛法）(代码片段)

题目背景在遥远的阿拉德大陆，有一种神秘的磁石，是由魔皇制作出来的，题目描述1.若给他一个一维坐标系，那么他的磁力一定要在素数坐标的位置上才能发挥的最大（不管位置坐标的大小，只要是素数那么磁力就一样大）2.... 查看详情

p3383模板线性筛素数(代码片段)

P3383【模板】线性筛素数埃氏筛->欧拉筛普通埃氏筛（O（nlognlogn））for(inti=2;i<=n;i++)//注意终止条件if(!notpri[i])for（intj=2;j*i<=n;j++）notpri[i*j]=true;优化for(inti=2;i<=n;i++)//到根号if(!notpri[i])for（intj=i;j*i<=n;j++）//j从i开始，因为... 查看详情

关于筛法

关于素数，有埃氏筛法O(nloglogn)，不过有更优的线性筛法，此线性筛法还可用于筛欧拉函数与莫比乌斯函数，作用很大1intcnt;2intprime[MAXN];3intpri[MAXN];4intphi[MAXN];5intmiu[MAXN];67/*素数筛*/8voidpre_prime(){9mem(prime,0);10cnt=0;11prime[0]=prime[1]=1;12f... 查看详情