线性筛质数

例子：30和45的最大公因数是15
设30为a, 15为b, 2为c
那c肯定会小于b, 因为b是最大公因数, 如果大于b, 那他(c)就是最大公因数, 所以不可能
c是质数, 因为假如c是质数, 那肯定可以分离个质数给b, 这样b就不是最大公因数了
所以, 是不是我们把(小于b的质数全部去乘以1~n）的数全部给标记了, 就可以了？
不是, 假如c大于b的最小质因数, 那30的最大公因数就不是b了
因为b是由若干个质数组成, 如果c大于b的最小质因数, 那b可以是会把自己最小的质因数和c换
所以, 当我们在遍历质数数组时, 它最多就是等于b的最小质因数

还有一个, 我们把从2开始的看作因数, 找他的质数, 第一层循环, 相当于从前往后去遍历一下所有的因数
第二层循环, 相当于把第一层循环中的i的后面的合数进行了标记, 并且根据质数不大于b的最小公因数, 去找后面的合数
如果质数与b的最小公因数相等, 那直接break

代码如下

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<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=1000010;
int primes[N];
bool st[N];
int ans;
void get_primes(int x)
{
	for(int i=2;i<=x;i++)
	{
		if(!st[i]) primes[ans++]=i;
		for(int j=0;primes[j]<=x/i;j++)
		{
			st[primes[j]*i]=true;
			if(i%primes[j]==0) break;
		}
	}
}
int main()
{
	int n;
	cin>>n;
	get_primes(n);
	cout<<ans<<endl;
	return 0;
}