素数筛

普通筛    时间复杂度 

bool vis[MAXN];

void primer()
{
	memset(vis, true, sizeof(vis));
	for (int i = 2; i <= n; i++)
	{
		if (vis[i] == true)
		{
			for (int j = 2; j * i <= n; j++)
				vis[i * j] = false;
		}
	}
}

Euler筛    时间复杂度 

const int MAXN = 1e7 + 5;
bool vis[MAXN];
int prime[MAXN];
int cnt = 0;
void Eluer()
{
	memset(vis, true, sizeof(vis));
	for (int i = 2; i <= MAXN; i++)
	{
		if (vis[i] == true)
		{
			prime[cnt++] = i;
		}
		for (int j = 0; j < cnt && i * prime[j] < MAXN; j++)
		{
			vis[i * prime[j]] = false;
			if (i % prime[j] == 0)
				break;
		}
	}
}

分解质因数   注意最后特判

void get(ll k)
{
	for (int i = 2; i * i <= k; i++)
	{
		if (k % i == 0)
		{
			v.push_back(i);
			while (k % i == 0)
				k /= i;
		}
	}
	if (k > 1)
		v.push_back(k);
}