关键词：
关于素数，有埃氏筛法O(nloglogn)，不过有更优的线性筛法，此线性筛法还可用于筛欧拉函数与莫比乌斯函数，作用很大
1 int cnt; 2 int prime[MAXN]; 3 int pri[MAXN]; 4 int phi[MAXN]; 5 int miu[MAXN]; 6 7 /* 素数筛 */ 8 void pre_prime(){ 9 mem(prime,0); 10 cnt = 0; 11 prime[0] = prime[1] = 1; 12 for(int i = 2 ; i < MAXN ; i++){ 13 if(!prime[i]) pri[cnt++] = i; 14 for(int j = 0 ; j < cnt && i * pri[j] <= MAXN ; j++){ 15 prime[i * pri[j]] = 1; 16 if(i % pri[j] == 0) break; 17 } 18 } 19 } 20 /* 莫比乌斯筛 */ 21 void pre_miu(){ 22 mem(prime,0); 23 cnt = 0; 24 miu[1] = 1; 25 for(int i = 2 ; i < MAXN ; i++){ 26 if(!prime[i]){ 27 miu[i] = -1; 28 pri[cnt++] = i; 29 } 30 for(int j = 0 ; j < cnt && i * pri[j] <= MAXN ; j++){ 31 prime[i * pri[j]] = 1; 32 if(i % pri[j] == 0){ 33 miu[i * pri[j]] = 0; 34 break; 35 }else miu[i * pri[j]] = -miu[i]; 36 } 37 } 38 } 39 /* 欧拉筛 */ 40 void pre_phi(){ 41 mem(prime,0); 42 cnt = 0; 43 phi[1] = 1; 44 for(int i = 2 ; i < MAXN ; i++){ 45 if(!prime[i]){ 46 miu[i] = -1; 47 pri[cnt++] = i; 48 } 49 for(int j = 0 ; j < cnt && i * pri[j] <= MAXN ; j++){ 50 prime[i * pri[j]] = 1; 51 if(i % pri[j] == 0){ 52 phi[i * pri[j]] = phi[i] * pri[j]; 53 break; 54 }else phi[i * pri[j]] = phi[i] * (pri[j] - 1); 55 } 56 } 57 }
「关于张博航提到的筛法的理解」——一种处理关于$p$成多项式的数论函数筛法
张博航原知乎网址 张博航原博客网址引入： 给一个完全积性函数$f$，求其前缀和 $$S(n)=\sum_i=1^nf(i)$$初步思考： 考虑由于所求函数为完全积性函数，我们很容易用一个线性筛在$O(n)$的时间负责度内解决问题。... 查看详情
线性筛法
关于线性筛法线性是指O（n）内筛掉所有合数，还有一种方法叫埃氏筛法，我先证明埃氏筛法效率低，也就是会有重复。证明如下：埃氏筛法的原理是找到一个素数后，它的1~n倍就会被筛掉，任何一个合数都可以被拆成一个质数*... 查看详情
数学基础素数线性筛法--欧拉筛法模板普通筛法的优化
...共同质因子的正整数称为互质1和0既非素数又非合数素数筛法原理：素数的倍数一定不是素数。实现步骤：用一个boook数组对maxn内的所有数进行标记，1为合数，0为素数，book 查看详情
线性筛法（欧拉筛法）求素数
时间复杂度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... 查看详情
一般筛法求素数+快速线性筛法求素数
...数较多，则先用下面介绍的办法预处理。 一般的线性筛法首先先介绍一般的线性筛法求素数voidmake_prime(){memset(prime,1,sizeof(prime));prime[0]=false;pri 查看详情
模板欧拉筛法（线性筛法）(代码片段)
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* 查看详情
转载一般筛法求素数+快速线性筛法求素数
...数较多，则先用下面介绍的办法预处理。 一般的线性筛法首先先介绍一般的线性筛法求素数 voidmake_prime(){ memset(prime,1,sizeof(prime)) 查看详情
线性筛法(代码片段)
...弄丢了，有谁看见我的脑子了，请联系我，谢谢！【线性筛法】线性筛法是啥，它是筛法。它降低了时空复杂度，如果用暴力的方法求素数，会爆时间。【模版】1#include<cstdio>2#include<cstring>3#defineMAXN1000054#defineMAXL12997105in... 查看详情
素数的快速筛法(埃氏筛法模板)(代码片段)
1intprime[maxn];//第i个素数2boolis_prime[maxn];//is_prime[i]为true表示i是素数3intsieve(intn)//返回n以内的素数45intcnt=0;6for(inti=0;i<=n;i++)7is_prime[i]=true;8is_prime[0]=is_prime[1]=false;9for(inti=2;i<=n;i++ 查看详情
埃氏筛法
/*2|埃式筛法|3|快速筛选素数| |15-7-26|4*/#include<iostream>#include<cstdio>usingnamespacestd;constintSIZE=1e7;intprime[SIZE];//第i个素数boolis_prime[SIZE];//true表示i是素数intslove(intn){intp=0;for(inti=0 查看详情
欧拉筛法（线性筛法）与解积性函数(代码片段)
日常吐槽：啧啧啧今天真是玄幻的一天。早上睡到9:10发现睡过了一个半小时，在9:30狂奔来机房+吃早餐，最后只剩一个半小时心态崩—>光荣爆零？？？又在下午四点把全部题改完？？？上午和下午的效率真的不是一个级别... 查看详情
筛法求莫比乌斯函数
素数筛法llpri[maxn],pri_num;llmu[maxn];//莫比乌斯函数值boolvis[maxn];voidmobius(){//筛法求莫比乌斯函数pri_num=0;//素数个数memset(vis,false,sizeof(vis));vis[1]=true;mu[1]=1;for(inti=2;i<maxn;i++){if(!vis[i]){pri[pri_num+ 查看详情
素数筛法
一、埃式筛法 埃式筛法的核心思想是从2到n枚举，当我们找到一个质数时，枚举它所有的倍数，因为这些倍数都不可能是质数。for(inti=2;i<=n;i++){if(!vis[i]){prime[++cnt]=i;for(intj=i*2;j<=n;j+=i)vis[j]=true;}}时间复杂度是O(nloglogn)如果... 查看详情
埃式筛法筛选素数pat1013(代码片段)
内容摘要：明确素数到底是啥数。埃式筛法是干嘛用的。利用java实现埃式筛法的思路。利用埃式筛法解决PAT_1013_B题。筛法的改进。素数(primenumber)到底是啥数：定义: 在大于1的自然数中，除了1和它本身以外不能再被其他... 查看详情
筛法求素数
问：求2000以内的素数？筛法求素数和暴力时间复杂度筛法求素数:O(N^2)暴力：O(N^N)原理：去掉1，最小的数是素数，然后将最小数的倍数全部去掉，直到最小的数到达范围为止用筛子把非素数全部筛出去。bool是C++中的一种数据类... 查看详情
素数的筛法(代码片段)
一写在开头1.1本文内容本文实现了素数的筛法算法。 二算法原理与实现在写代码的过程中，时不时会遇到求解素数的任务，特意将素数求解方法总结成文章以备不时之需。素数的求解算法大概有两种。一种是枚举某一范围的... 查看详情
线性筛法(代码片段)
线性筛法上节课讲的是Eratosthenes筛法利用的原理是任意整数x的倍数2x，3x，...等都不是质数。但是即便如此也会有重复标记的现象，例如12既会被2又会被3标记，在标记2的倍数时，(12=6*2)，在标记3的倍数时，(12=4*3)，根本原因是没... 查看详情
练习筛法遍历素数（java）(代码片段)
...个练习题是暴力遍历素数。因为看过av32186751，知道有个筛法，就想试试。 又受到线性筛法（一）--素数筛法（一）-nerd呱呱-博客园中，的这段启发，就有了下面的代码。 引用文字：我们先定义一个数组来存100000以内数是... 查看详情