【模板】找素数&找约数（唯一分解定理）

前排提示：唯一分解定理

试除法，遍历。

简单好写，询问过多时易超时。

const int N=1e7+5;
int p[N],v[N],cnt=0;
void prime()
{
    for(int n=2;n<N;n++)
        for(int i=2;i<=n;i++)
        {
            if(n%i==0)
                break;
        }
}

朴素筛法，对每一个数不断将其倍数标记，最后剩下的自然是质数。

要建立数组在存每个数并标记，占内存写起来麻烦但是快。->1.628

const int N=1e7+5;
int p[N],v[N],cnt=0;
void prime()
{
	int i,j;
	for(i=2;i<N;i++)
	{
		if(v[i]==0)
			p[cnt++]=i;
		for(j=i*2;j<N;j+=i)
			v[j]=1;
	}
}

埃氏筛法，只将每个质数的倍数不断标记，剩下的数就是质数。

大幅减少循环次数，再次缩短时间。->0.400

const int N=1e7+5;
int p[N],v[N],cnt=0;
void prime()
{
	int i,j;
	for(i=2;i<N;i++)
	{
		if(v[i]==0)
		{
			p[cnt++]=i;
		    for(j=i*2;j<N;j+=i)
			    v[j]=1;
		}
	}
}

线性筛法，每个数只会被其最小质数标记一次。

当输入小于1e6时，与埃氏筛法差距不大，随输入增大时间优势越来越大。->0.135s

const int N=1e7+5;
int p[N],v[N];
void prime()
{
	int i,j,k,cnt=0;
	for(i=2;i<N;i++)
	{
		if(!v[i])
			p[cnt++]=i;
		for(j=0;p[j]*i<N;j++)
		{
			v[p[j]*i]=1;
			if(i%p[j]==0)
				break;
		}
	}
}

求约数的个数

约数个数定理：一个合数,若其自身与其所有质因子幂次方的积大小相等,则约数个数等于所有幂次方加一后的积.

基于线性筛法的约数个数定理的实现

//基于线性筛法的约数个数定理的实现
#include <iostream>
#include<vector>
using namespace std;
const int array_size = (int) 1e5+50;  
int prime[array_size],vis[array_size],approx[array_size];
void slove()
{
    int cnt = 0;
    for (int i = 2; i < array_size; i++)
    {
        if (!vis[i])
        {
            prime[cnt++] = i;
            approx[i] = 2;
        }
        for (int j = 0; prime[j] * i < array_size; j++)
        {
            vis[prime[j] * i] = 1;
            if (i % prime[j] == 0)
            {
                int sum = 0, num = i;
                while (num % prime[j] == 0)
                {
                    num /= prime[j];
                    sum++;
                }
                //显然,i*prime[j]相比i多乘了prime[j],则其约数为approx[i]*(x+1/x),x为最后一个质因子的幂次方
                approx[i * prime[j]] = approx[i] / (sum + 1) * (sum + 2);
                break;
            }
            //若x=i*j,则approx[x]=approx[i]*approx[j];
            else approx[i * prime[j]] = approx[i] * approx[prime[j]];
        }
    }
    return;
}
int main()
{
    slove();
    int n;
    while (cin >> n && n)
        cout << approx[n] << endl;
    return 0;
}

求给定数的约数个数

//求给定数的约数个数，依然是约数个数定理的应用。
//原理1:任何一个数都可以转化为质数幂次方的和.原理2.若一个数等于质数幂次方的和,则它的约数个数等于所有幂次方均+1后的积.
#include<map>
#include<queue>
#include<cmath>
#include<string>//使用to_string必须加该头文件
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long 
#define itn int
const int array_size = (int)1e6 + 50;
const int INF = 0x3f3f3f3f;
using namespace std;
int p[array_size], v[array_size];
void slove()
{
	int cnt = 0;
	for (int i = 2; i < array_size; ++i)
	{
		if (!v[i])p[++cnt] = i;
		for (int j = 1; p[j] < array_size / i; ++j)
		{
			v[p[j] * i] = 1;
			if (i % p[j] == 0)break;
		}
	}
	p[0] = cnt;
	return;
}
int main()
{
	slove();
	int k = 1200000,cnt = 1;
	vector<int>c;
	while (k > 1)
	{
		int f = 0;
		while (k % p[cnt] == 0)
		{
			k /= p[cnt];
			f++;
		}
		if (f)c.push_back(f);
		cnt++;
	}
	int ans = 1;
	for (int i = 0; i < c.size(); ++i)
		ans *= (c[i] + 1);
	cout << ans;
	return 0;
}