正文

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

zhengkunjia  zhengkunjia  2023-04-22  417

关键词：

P3383 【模板】线性筛素数

埃氏筛->欧拉筛

普通埃氏筛（O（nlognlogn））

for (int i = 2; i <= n; i++)//注意终止条件

    if(!notpri[i])
        for（int j = 2; j * i <= n; j++）
            notpri[i*j]=true;

优化

for (int i = 2; i <= n; i++)//到根号

    if(!notpri[i])
        for（int j = i; j * i <= n; j++）//j从i开始，因为[2、3..i - 1] * i之前再筛[2、3..i - 1]时已经筛过
            notpri[i*j]=true;

但这样还有重复！
比如24，删2时、删3时、删4时，都删了一次！（12,8,6被优化省了）

欧拉筛（线性筛）

思想：让每个合数只被最小质因数筛去

过程（摘自[_mliy]（https://www.luogu.com.cn/blog/222223/solution-p3383））

避免重复筛，应找到筛合数的一种原则：这个合数只会被它的最小质因数筛。这样能保证每个合数只会被筛一次。
（运行过程）从 22 开始，22 加入 prime 数组，再从小到大枚举质数（现在只有 22），筛掉质数与 22 的乘积（44 被筛掉）。
到了 33，33 加入 prime 数组，从小到大枚举质数（此时有 22,33），筛掉质数与 33 的乘积（66,99 被筛掉）。到了 44，44 没加入 prime 数组，枚举质数（有22,33），筛掉 88 后，因为 4mod2=04mod2=0，触发退出条件。（不触发，就会筛掉 1212，而 12=2 imes 2 imes 312=2×2×3，又会被 22 和 66筛一次）
以此类推，可做出一张表：

ii 的值质数表筛去的数
2 2 4
3 2，3 6，9
4 2，3 8
5 2，3，5 10，15，25
6 2，3，5 12
7 2，3，5，7 14，21，28，35
cdots? cdots? cdots?
每个质数只被筛一次，复杂度变为 O(n)O(n) ，可以AC。

理解（摘自彤云望月）

对于 i%prime[j] == 0 就break的解释：当 i是prime[j]的倍数时，i = kprime[j]，如果继续运算 j+1，i * prime[j+1] = prime[j] * k prime[j+1]，这里prime[j]是最小的素因子，当i = k * prime[j+1]时会重复，所以才跳出循环。
举个例子：i = 8 ，j = 1，prime[j] = 2，如果不跳出循环，prime[j+1] = 3，8 * 3 = 2 * 4 * 3 = 2 * 12，在i = 12时会计算。因为欧拉筛法的原理便是通过最小素因子来消除。

for（int i = 2; i <= sqrt(n); i++）

    if(!notpri[i])    pri[++len] = i;
    for (int j = 1; j <= len; j++)
    
        notpri[i * pri[j]] = true;
        if(i % pri[j] == 0)    break;

题目ACcode

#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define N 100000010
#define F(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

int n, q, notpri[N], pri[10000000], k,len;

void pre()

    for(int i = 2; i <= n; i++)
        if(!notpri[i])  pri[++len] = i;
        for(int j = 1; j <= len; j++)
            if(i * pri[j] >= n) break;
            notpri[i * pri[j]] = 1;
            if(i % pri[j] == 0)     break;
        
    


int main()

    scanf("%d%d",&n ,&q);
    pre();
    while(q--)
        scanf("%d",&k);
        printf("%d
",pri[k]);
    
//  cout << len << "**";
    return 0;

反思

此题做了两天，总是RE，找了好久才知道是i*pri[j]没判断<=n!!!

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开始，因为... 查看详情

线性筛洛谷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... 查看详情

洛谷p3383模板线性筛素数

p3383模板线性筛素数

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

p3383模板线性筛素数

题目描述如题，给定一个范围N，你需要处理M个某数字是否为质数的询问（每个数字均在范围1-N内）输入输出格式输入格式：第一行包含两个正整数N、M，分别表示查询的范围和查询的个数。接下来M行每行包含一个不小于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模板线性筛素数

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

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

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

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

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

线性筛求素数1#include<iostream>2#include<cstring>3#include<algorithm>4#include<cstdio>56constintMAX_N=10000000+10;78boolvis[MAX_N];9intPrime[MAX_N>>1];10inlinevoidGetPrime(intn 查看详情

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

memset(check,false,sizeofcheck);inttot=0;for(inti=2;i<=N;++i)if(!check[i])prime[tot++]=i;for(intj=0;j<tot;++j)if(i*prime[j]>N)break;check[i*prime[j]]=true;if(i%prime[j]==0)break; 查看详情

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

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

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

我太菜了%韩神1#include<iostream>2#include<cstdio>3#include<cmath>4#include<cstdlib>5#include<cstring>6#include<algorithm>7#include<vector>8#include<queue>9#de 查看详情

浅谈线性素数筛(代码片段)

...小的质因数筛掉它，所以时间复杂度保证是线性的。　　模板：https://www.luogu.org/problemnew/show/P3383代码：1#include<iostream> 查看详情