欧拉筛法

发表于

勤奋tc又来了这回是欧拉筛法
先从头开始吧，一般的素数筛选基本就是从1开始计算然后一直除到那个数为止。基本就是两个for循环

1
2
3
4
5
6
7
8
for(int i = 0;i <= sqrt（n）;i++)
{
	for(int j = 2;j < i;j++)
	{
		if(i%j) break;
	}
	if(j == i) num[k++] = i;
}

这一种的复杂度很大大概是o（n * sqrt（n））这是一种复杂度很大的算法，一般不会用这个。这里就有一个欧拉筛法了，时间复杂度大概在o（n）左右我们可以知道，每一个素数的n倍都是合数，所以我们找到一个素数的时候就可以将他的n次倍都标计。
以下是代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
using namespace std;

int num[1000000];
bool vis[100000];


void f(int a) {
	int i = 2;
	for(i; i <= a; i++) {
		if(!vis[i])
			num[++num[0]] = i;
		int len = num[0];
		int j = 1;
		for(j; j <= len && i * num[j] <= a; j++) {
			vis[i * num[j]] = true;
			if(i%num[j] == 0) break;
		}
	}
}

int main() {
	int n;
	cin>>n;
	f(n);
	int len = num[0];
	for(int i = 1; i <= len; i++) cout<<num[i]<<" ";
	return 0;
}

一个合数有可能不止一个因数，所以这样写的话可能就会导致一个数被重复标记，这样会多余耗时很多，所以我们在这添加一步，i%num[j] == 0 break； 当num[j]是i的因数时，说明i有多个因数，他的更大的倍数可以由其他的更大的数来筛选掉，后面的筛选就没有必要了，所以从这里跳出循环。