素数打表法

定义法

素数的定义:

  • 只能被1和本身整除的数。

适用范围:

  • 适合判断单个数是否为素数
  • 若是求一个大范围内的所有素数,此方法耗时太长

代码:

/*判断n是否为素数*/
for(i=2;i*i<=n;i++) {
	if(n%i==0) {
		flag=0;/*flag=0代表n不是素数*/
		break;
	}
}

普通筛选法/埃氏筛法

思想:

  • 首先假定所求范围内的所有数都是素数,然后去除该范围内的所有合数,剩下的全是素数。
  • 任何合数均可表示为素数的倍数。因此,如果已知一个数是素数,那么它的倍数都是合数。

代码:

int not_prime[MAXN]={0};/*假定所有数都是素数*/
for(int i=2;i<=sqrt(MAXN);i++) {
	if(!not_Prime[i]) {/*如果i是素数*/
		for(j=i*i;j<=MAXN;j+=i) {/*那么i的倍数全是合数*/
			not_prime[i]=1;
		}
	}
}

注意事项:

  • 为什么第二重循环里j的初始值为i* i呢?这是为了避免重复标记。举个例子,若i是素数,那么2* i、3* i、4* i……(i-1)* i分别是2、3、4……(i-1)的倍数,在外层循环循环到i之前就已经被标记为合数了。所以应该从j=i* i开始,依次把j+i、j+2* i……标记为合数。

缺陷:

对于一个合数,可能被重复筛选多次。

线性筛选法/欧拉筛法

思路:

欧拉筛法是埃氏筛法的改进版,大体思路都是先假定所有数都是质数,然后把所有合数去除,留下的都是质数;不同之处就是去除合数的方法,欧拉筛法保证了每个合数只会被它的最小质因数筛去。虽然代码有两重循环,但是因为待求范围内的每个数均只被筛选1次,所以时间复杂度是O(n)。

代码:

bool visit[MAXN]={0};/*visit数组存的是待求范围的所有自然数*/
/*visit[1]=0表示1是素数*/
int prime[MAXL]; /*prime数组只存待求范围内的素数*/
/*MAXL可以根据MAXN的大小大致估计一下,MAXN一般是题目给出*/
int cnt=0; /*cnt用来记录素数的个数*/
void getprime(int n)
{
	for(int i = 2;i <= n;i++) {
		if(!visit[i]) prime[cnt++]=i;/*如果i是素数,就把i标记在prime数组里*/
		for(j = 0;i * visit[j] < n && j < cnt;j++) {
			visit[i * prime[j]] = 1;/*prime数组里面存的素数的i倍,都标记为合数*/
			if(i % prime[j] == 0) break;/*关键,看后面的解释*/
		}
	}
}
``
### 解释:
    为什么说欧拉筛法保证了每个合数只会被它的最小质因数筛去呢?
    关键是这一行:

```c
if(i % prime[j] == 0) break;

接下来分类讨论一下:

  1. 如果i % prime[j] != 0,prime[j]一定小于i的最小质因数,所以prime[j]一定是i* prime[j]的最小质因数。
  2. 如果i % prime[j] == 0,
    (1)prime[j]就是i的最小质因数(因为j是从小到大枚举的),此时prime[j]依旧是是i* prime[j]的最小质因数。
    (2)但是j++后的下一个prime[j],就大于i的最小质因数,故prime[j]不是i* prime[j]的最小质因数。所以才要在i % prime[j] == 0的时候break。

学自大佬,欢迎交流批评指正。

上一篇:二叉树基本操作


下一篇:Hive系统函数之collect_list和collect_set