【模板】素数筛法和质因数分解（素数、质因数分解题解）

最新推荐文章于 2024-04-30 22:19:02 发布

coderwait

最新推荐文章于 2024-04-30 22:19:02 发布

阅读量597

点赞数

分类专栏：算法理论和模板

本文链接：https://blog.csdn.net/coderwait/article/details/89459768

版权

算法理论和模板专栏收录该内容

31 篇文章

订阅专栏

素数筛法

常规思路：如果 $n$ 能被 $i$ $(2\leq i \leq \sqrt{n})$ 整除，则不是素数。

素数筛选：换一个角度。当获得一个素数的时候，就把它的所有倍数标记为非素数。这样，当我们遍历到一个数时，如果其已经被标记，则说明存在一个更小的数，是它的因子，因此它不是素数，否则它是素数。

素数

题目描述

输入一个整数n(2<=n<=10000)，要求输出所有从1到这个整数之间(不包括1和这个整数)个位为1的素数，如果没有则输出-1。

输入描述:

输入有多组数据。每组一行，输入n。

输出描述:

输出所有从1到这个整数之间(不包括1和这个整数)个位为1的素数(素数之间用空格隔开，最后一个素数后面没有空格)，如果没有则输出-1。

输入

输出

11 31 41 61 71

#include<iostream>
using namespace std;
bool mark[10001];
int prime[10001]; //记录我们筛选出来的素数 
int primeSize;//筛选的素数个数 
void init()
{
	primeSize=0; 
	for(int i=1;i<10001;i++){
		mark[i]=false;
	}
	for(int i=2;i<10001;i++){
		if(mark[i]==true) continue;//如果被标记了，说明它是某个数的倍数 
		prime[primeSize++]=i;//否则说明它不被任何大于等于2的整除，是素数 
		for(int j=i*i;j<10001;j=j+i){//从i*i开始遍历i的倍数 
			mark[j]=true;	
		}
	} 
}int main(void) 
{
	init();
	int n;
	while(cin>>n){
		int count=0;
		for(int i=0;i<primeSize;i++){
			if(prime[i]<n&&prime[i]%10==1){
				if(count==0) cout<<prime[i];
				else cout<<" "<<prime[i]; 
				count++;
			}
		}
		if(count==0) cout<<"-1";
		cout<<endl;
	}
}

最朴素的素数判定：

#include<bits/stdc++.h>
using namespace std;
int judge(int n)
{
	if(n<=1) return false;
	for(int i=2;i*i<=n;i++)
	{
		if(n%i==0) return false;
	}
	return true;
}
int main(void)
{
	int n;
	while(cin>>n)
	{
		puts(judge(n)?"yes":"no");
	}
	return 0;
}

质因数分解

首先筛选出素数，然后只要能被素数整除，就依次用n去除以该素数。如果不能被该数继续整除就选择下一个素数。直到为1。

技巧：这里只筛选了100000以内的素数，这是因为如果存在比100000大的素数因子，则一定没有被除到1且这样的素数因子一定只有1个。

质因数的个数

题目描述

求正整数N(N>1)的质因数的个数。相同的质因数需要重复计算。如120=2*2*2*3*5，共有5个质因数。

输入描述:

可能有多组测试数据，每组测试数据的输入是一个正整数N，(1<N<10^9)。

输出描述:

对于每组数据，输出N的质因数的个数。

输入

输出

#include<iostream>
using namespace std;
bool mark[100001];
int prime[100001]={0};
int primeNum=0;
void init()
{
	//素数筛选
	for(int i=0;i<100001;i++) mark[i]=false;
	for(int i=2;i<100001;i++)
	{
		if(mark[i]==true) continue;
		else{
			mark[i]=false;
			if(i>=1000) continue;
			for(int j=i*i;j<100001;j+=i)
			{
				mark[j]=true;
			}
		}
	 } 
	 for(int i=2;i<100001;i++)
	 {
	 	if(mark[i]==false)
	 	{
	 		prime[primeNum]=i;
		 	primeNum++;	
		 }
	 }
}
int main(void)
{
	init();
	int n;
	while(cin>>n)
	{
		int ans=0;
		for(int i=0;i<primeNum;i++)
		{
			if(n%prime[i]==0)
			{
				while(n%prime[i]==0)
				{
					ans++;
					n=n/prime[i];
				}
			}
		}
		if(n!=1) ans++;
		cout<<ans<<endl;
	}
	return 0;
}