关键词：
质数（素数）：指大于1的所有自然数中，除了1和自身，不能被其它自然数整除的数
合数：比1大，但不是素数的数称为合数，合数除了被1和自身整除，还能被其它数整除
质因数（素因数或质因子）：能整除给定正整数的质数，除1以外，两个没有其它共同质因子的正整数称为互质
1和0既非素数又非合数
素数筛法原理：素数的倍数一定不是素数。
实现步骤：用一个boook数组对maxn内的所有数进行标记，1为合数，0为素数，book初始化为0是假设全部数都为素数，从第一个素数2开始，把2的倍数标记为1，然后继续下一轮
欧拉筛法与普通筛法比较，优化之处在于每个合数不会被重复标记，时间复杂度和空间复杂度均为o(n)
#define maxn 100005 #define maxl 1299710 int prime[maxn],book[maxl]; void prime() { int i,sum=0,j; memset(book,0,sizeof(book)); for(i = 2; i < 2500000; i ++) { if(!book[i]) prime[sum++] = i; for(j = 0; j < sum; j ++)//保证合数只会被它的最小质因数筛去 ，因此每个数只会被筛去一次 { if(i*prime[j] >= maxl) break; book[i*prime[j]] = 1; if(i%prime[j] == 0) break; } } return; }
[模板]线性筛素数(欧拉筛法)(代码片段)
用途$O(n)$处理出n以内所有素数原理使用合数=最大因数(除1和本身外)*最小质因数的原理来筛，每个数只会被筛一次对于每个数i，令它是某数的最大因数，然后从小到大地找<=i的素数j，则i*j是合数直到找到某个j使得$i\%j==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 查看详情
素数筛法
筛素数弱智筛法就不贴了下面是埃氏筛先补一个很有意思的东西1+1/2+1/3+1/4+....+1/n=logn线性筛代码 欧拉函数 对于大范围内求质因数个数硬解肯定太慢，用线性筛优化先用线性筛找到每一个数的最小质因子(rec[i... 查看详情
模板欧拉筛法（线性筛法）(代码片段)
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* 查看详情
『素数(prime)判定和线性欧拉筛法(thesieveofeuler)』(代码片段)
素数(Prime)及判定定义素数又称质数，一个大于1的自然数，除了1和它自身外，不能整除其他自然数的数叫做质数，否则称为合数。1既不是素数也不是合数。判定如何判定一个数是否是素数呢？显然，我们可以枚举这个数的因数... 查看详情
[洛谷p3383]线性筛素数-欧拉筛法
Description如题，给定一个范围N，你需要处理M个某数字是否为质数的询问（每个数字均在范围1-N内）Input&OutputInput第一行包含两个正整数N、M，分别表示查询的范围和查询的个数。接下来M行每行包含一个不小于1且不大于N的整数... 查看详情
关于筛法
关于素数，有埃氏筛法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... 查看详情
浅谈线性素数筛(代码片段)
素数筛的用处还是蛮多的，有很多和素数有关的题都要用到素数筛，所以有一个高效的筛法自然是非常好的吖，普通筛法（暴力筛法）就不说了，因为有了高效的也没人在会用普通筛法了吧。 线性素数筛是用每一个合数... 查看详情
一般筛法求素数+快速线性筛法求素数
素数总是一个比较常涉及到的内容，掌握求素数的方法是一项基本功。基本原则就是题目如果只需要判断少量数字是否为素数，直接枚举因子2。。N^(0.5)，看看能否整除N。如果需要判断的次数较多，则先用下面介绍的办法预处理... 查看详情
欧拉筛法求素数
欧拉筛法求素数 首先，我们知道当一个数为素数的时候，它的倍数肯定不是素数。所以我们可以从2开始通过乘积筛掉所有的合数。 将所有合数标记，保证不被重复筛除，时间复杂度为O（n）。代码... 查看详情
转载一般筛法求素数+快速线性筛法求素数
素数总是一个比较常涉及到的内容，掌握求素数的方法是一项基本功。基本原则就是题目如果只需要判断少量数字是否为素数，直接枚举因子2。。N^(0.5)，看看能否整除N。如果需要判断的次数较多，则先用下面介绍的办法预... 查看详情
基础算法——筛法求素数(代码片段)
以下来自http://blog.csdn.net/stack_queue/article/details/53560887求素数是程序设计比赛中经常遇到的问题，最基本的方法是通过素数的定义直接判断，只能被1和它本身整除的数就是素数了。这种方法适合判断单个数是否为素数，当要求一... 查看详情
线性筛法
...也就是会有重复。证明如下：埃氏筛法的原理是找到一个素数后，它的1~n倍就会被筛掉，任何一个合数都可以被拆成一个质数*合数的形式，我们对每一个质数对应的可能的（合）数都枚举了，这就保证了所有可能的合数都被筛... 查看详情
普通方法求素数与筛法求素数比較
普通方法求素数与筛法求素数比較20150806packageday06;/**普通方法求素数与筛法求素数比較*/importjava.util.*;publicclassTestSushu{ publicstaticvoidmain(String[]args){ Scannerscan=newScanner(System.in); System.out.print("查找范围2～"); in 查看详情
欧拉筛法
作用：求出[2,N]内所有素数。算法：每个合数必有一个素数因子，利用已知素数去筛除合数。说明：因为答案数组是从1开始的，所以用binary_search()、lower_bound()和upper_bound()函数不需要另行判断，但注意写法要均加1 ---------------... 查看详情
欧拉函数线性筛法
1#include<iostream>2#include<cstdio>3#include<cstring>4#include<cmath>5#definellilonglongint6usingnamespacestd;7constintMAXN=10000001;8voidread(int&n)9{10charc=‘+‘;intx=0;b 查看详情
埃式筛法筛选素数pat1013(代码片段)
内容摘要：明确素数到底是啥数。埃式筛法是干嘛用的。利用java实现埃式筛法的思路。利用埃式筛法解决PAT_1013_B题。筛法的改进。素数(primenumber)到底是啥数：定义: 在大于1的自然数中，除了1和它本身以外不能再被其他... 查看详情
线性筛
在这里提供三种线性筛的讲解,它们分别是:素数筛,欧拉筛和莫比乌斯筛。 ·筛法正确性的重要理论依据：上述函数均为积性函数。积性函数的性质为:若f(x)是一个积性函数,那么对于任意素数a,b,满足f(ab)=f(a)*f(b) ·一些可爱... 查看详情