质数.md

#试除法判断质数 直接从2开始，到sqrt(n)为止，如果能除以就不是质数，反之就是质数。

#分解质因数

从i=2开始到根号N结束，如果遇到N的因子就不断相除直到n不能再除为止。

# include<bits/stdc++.h>
using namespace std;
typedef long long ll;

void divide(ll n)
{
	
	for(int i=2;i<=n/i;i++)
	{
		ll s=0;
		if(n%i==0)
		{
			while(n%i==0)
			{
			n/=i;s++;
			}
			cout<<i<<" "<<s<<endl;
			
		}
	}
	
	if(n>1)
	cout<<n<<" 1"<<endl;
	
}
int main (void)
{
	cin.tie(0);
	cout.tie(0);
	
	ll n;
	cin>>n;
	while(n--)
	{
		ll x;
		cin>>x;
		divide(x);
		cout<<endl;
		
		
	}
	
	return 0;
		
}

#埃式筛

原理是最基本的分解质因数。

题目：计算从一到n有多少个质数。

# include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n;
bool judge[10005];
ll ans;
void ifjudge()
{
	
	for(int i=2;i<=n;i++)
	{
		if(!judge[i])
		{
			ans++;
			for(int j=i+i;j<=n;j+=i)    //依次去除每个质因子i的整数倍
			{
				judge[j]=true;	
			}		
		}
	}
}

int main (void)
{
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;
	ifjudge();
	cout<<ans<<endl;
	
	
	return 0;
		
}

#欧拉筛

P3383 【模板】线性筛素数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

欧拉筛的基本思想是，找到所有以i为最大质因子的数，并以此将他们筛去。

# include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
bool st[100000005];
ll primes[100000005];
ll cnt;
void get_primes(ll n)
{
	for(int i=2;i<=n;i++)
	{
		if(!st[i])
		primes[cnt++]=i;
		for(int j=0;primes[j]<=n/i;j++)   //防越界
		{
			st[primes[j]*i]=true;
					if(i%primes[j]==0)    //如果primes[j]是i的质因子，那么退出，也是防越界
			break;	
		}	
	}
	
}
int main (void)
{
	std::ios::sync_with_stdio(false);
	cout.tie(0);
	cin.tie(0);
	scanf("%d",&n);
	get_primes(n);
	
	ll q;
	scanf("%d",&q);
	while(q--)
	{
		ll ask;
		scanf("%d",&ask);
		
		printf("%d\n",primes[ask-1]);
		
		
		
	}
		
}