正文

欧拉筛（线性筛）

author  author  2022-09-13  191

关键词：

素数筛，就是按照顺序把合数踢掉，剩下的是素数。

欧拉筛是一种O（n）求素数的筛法。他避免了埃拉特斯特尼筛法对同一数的多次筛除。

欧拉筛的原理是只通过数的最小质因数筛数。

先上代码：

#include <cstdio>
using namespace std;

const int maxn=10000000;
int n, m, prime[maxn], isnt_prime[maxn], tot;

void get_prime(int n){
    isnt_prime[0]=isnt_prime[1]=1;
    for (int i=2; i<=n; ++i){
        if (!isnt_prime[i]) prime[++tot]=i;
        for (int j=1; j<=tot&&i*prime[j]<=n; ++j){
            isnt_prime[i*prime[j]]=1;
            if (i%prime[j]==0) break;
        }
    }
}

int main(){
    scanf("%d%d", &n, &m);
    get_prime(n);
    int t;
    for (int i=0; i<m; ++i){
        scanf("%d", &t);
        if (!isnt_prime[t]) printf("Yes
");
        else printf("No
");
    }
    return 0;
}

对于当前处理数i，我们将i分解成p1*p2*p3……，当前枚举素数为p[j]。

由于j从小到大枚举，直到i%p[j]==0前，p[j]都是i*p[j]的最小质因数。

在i%p[j]==0后，由于p[j]不是i*p[j]的最小质因数，i*p[j]必然可以被一个更小的质数q筛去。而i*p[j]/q必然会在后面被访问。所以不用遍历。

如何证明复杂度呢？由于2道n区间内的每一个数，都一定只被最小质因数筛掉，所以第二个for循环均摊到n个元素上的时间复杂度是O（1），总时间复杂度就是O（N）。

这是本人对欧拉筛的一点理解，如果有更好的方法或解释，欢迎在评论区评论。。

欧拉线性筛(代码片段)

筛质数关于欧拉筛筛质数，其总体思想：·首先，假设所有的数都是质数，然后通过筛选将合数一一筛去·为了确保可以在线性时间内筛去所有的合数(即对于每一个数只处理一次)，每一个合数只由其最小的质因数筛去一次，从而... 查看详情

sumofconsecutiveprimenumberspoj-2739线性欧拉筛（线性欧拉筛证明）(代码片段)

题意：给一个数可以写出多少种连续素数的合思路：直接线性筛筛素数暴力找就行 (素数到n/2就可以停下了,优化一个常数)其中：线性筛的证明参考：https://blog.csdn.net/nk_test/article/details/46242401　　　　　　　　　　　... 查看详情

线性筛

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

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

时间复杂度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... 查看详情

noip复习——线性筛(欧拉筛)(代码片段)

整数的唯一分解定理：\(\forallA\in\mathbbN,\,A>1\quad\exists\prod_i=1^sp_i^a_i=A\)，其中\(\displaystylep_1<p_2<p_3<\cdots<p_s\)而且\(p_i\)是一个质数,\(a_i\in\mathbbZ^+\)(摘自维基百科查看详情

欧拉筛&&线性筛(代码片段)

复杂度n分析其实就是把埃筛的改进罢了，避免重复具体看代码代码#include<bits/stdc++.h>usingnamespacestd;boolvis[10000000];intprime[10000];intOulashai(intn)memset(vis,0,sizeof(vis));intcnt=0;for(inti=2;i<=n;i++)if(!vis[i])p 查看详情

模板欧拉筛法（线性筛法）(代码片段)

1intn;2intp[MAX_N],cnt;3boolb[MAX_N];45voidEuler()67b[0]=b[1]=1;8for(registerinti=2;i<=n;++i)910if(!b[i])p[cnt++]=i;11for(registerintj=0;i*p[j]<=n;++j)12//不需要判断j<cnt，因为中途定然会break出去1314b[i* 查看详情

theeulerfunction（线性筛欧拉函数）

...：暴力搞一下，打表#放弃：打了十几分钟没打完#改进：欧拉函数：具体证明看po主的博客^0^#超时：这里直接用欧拉函数暴力搞还是不可以的,用到线性筛欧拉函数，这里总和爆int，要用longlong*/#include<bits/stdc++.h>#definell 查看详情

欧拉筛线性处理莫比乌斯函数(代码片段)

欧拉筛线性处理莫比乌斯函数代码#include<bits/stdc++.h>usingnamespacestd;constintN=1e6+5;intprime[N];boolvis[N];intmobius[N];voidinit()inttimes=0;for(inti=2;i<N;i++)if(!vis[i 查看详情

欧拉函数线性筛法

1#include<iostream>2#include<cstdio>3#include<cstring>4#include<cmath>5#definellilonglongint6usingnamespacestd;7constintMAXN=10000001;8voidread(int&n)9{10charc=‘+‘;intx=0;b 查看详情

线性筛欧拉函数

#include<bits/stdc++.h>usingnamespacestd;intP[40005]={1,1},phi[40005];vector<int>prime;voidgetphi(intn){for(inti=2;i<=n;i++){if(!P[i])prime.push_back(i),phi[i]=i-1;for(intj=0;j<prime 查看详情

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

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

线性欧拉筛(代码片段)

//欧拉函数小于等于n且与n互质的正整数个数#include<bits/stdc++.h>usingnamespacestd;constintN=100001;intn,p;intprime[N],phi[N],mark[N];intmain()cin>>n;phi[1]=1;for(inti=2;i<=n;++i)if(!mark[i])prime[++p]= 查看详情

poj3126primepath（bfs+欧拉线性素数筛）

DescriptionTheministersofthecabinetwerequiteupsetbythemessagefromtheChiefofSecuritystatingthattheywouldallhavetochangethefour-digitroomnumbersontheiroffices.—Itisamatterofsecuritytochangesuchthingseve 查看详情

欧拉线性筛模板

memset(mindiv,0,sizeof(mindiv));for(inti=2;i<=n;i++){if(!mindiv[i])prime[++tot]=mindiv[i]=i;for(intj=1;j<=tot&&prime[j]<=mindiv[i]&&(k=prime[j]*i)<=n;j++)mindiv[k]=prime[j] 查看详情

线性筛素数（欧拉筛）(代码片段)

线性筛素数解题思路这题n很大用埃式筛O(n loglog n)O(n~loglog~n)O(n loglog n)还是会超时的所以就用线性筛O(n)O(n)O(n)AC代码#include<cstdio>usingnamespacestd;intn,q,tot,prime[6000005];boola[100000005];voidprimes()//线性筛 for(inti=2;i<=n;i++)... 查看详情

线性筛素数（欧拉筛）(代码片段)

[bzoj2818]gcd（数论，欧拉函数，线性筛）

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2818 必须用线性筛。1#include<bits/stdc++.h>2usingnamespacestd;3typedeflonglongLL;4constintmaxn=10001001;5LLphi[maxn],sum[maxn],n;6boolisprime[m 查看详情