I Older Brother（质因子分解）

本文主要是介绍I Older Brother（质因子分解），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目


题意：q=p^k(p为素数，k>=1)问是否能找到这样的p素数；
思路：1.基本方法：数据是1e9;时间是1s,1s最多跑3e8;
优化一下若是素数直接输出yes;否则利用素数筛把所有的素数存放起来，暴力试探是否q=p^k;
2.质因子分解定理（算数基本定理）：任何一个大于 1 的整数都能唯一分解为有限个质数的乘积。

AC代码
1

#include <bits/stdc++.h>using namespace std;
#define ll long long
const int maxn=1e6+11;//不能触及到边界，否则4这种数据输出no
int prime[maxn];
int vis[maxn];
int top;
void prim()//素数筛法筛选素数
{for(int i=2; i<maxn; i++)vis[i]=1;vis[0]=vis[1]=0;top=0;for(int i=2; i<maxn; i++){if(vis[i]==1){prime[++top]=i;for(int j=2*i; j<maxn; j+=i){vis[j]=0;}}}
}
int judge(int n)//判断素数法
{if(n<=1)return 0;else{for(int i=2; i<=sqrt(n); i++){if(n%i==0)return 0;}}return 1;
}
int main()
{prim();int n,ans;cin>>n;if(n==1)cout<<"no"<<endl;else{if(judge(n)==1)cout<<"yes"<<endl;else{for(int i=1; i<=top; i++){ans=1;//初始化while(ans<n){ans=ans*prime[i];}if(ans==n){break;}}if(ans==n)cout<<"yes"<<endl;elsecout<<"no"<<endl;}}return 0;
}

2

#include <bits/stdc++.h>using namespace std;
set<int>s;//set作为一个容器用来存储同一数据类型的数据类型,自动排序，去重；
int main()
{int x,q;cin>>x;q=x;for(int i=2; i<=sqrt(q); i++)//质因子分解定理{while(x%i==0){s.insert(i);x=x/i;}}if(x!=1)s.insert(x);//很关键的一步，例如37if(s.size()==1)cout<<"yes"<<endl;elsecout<<"no"<<endl;return 0;
}

这篇关于I Older Brother（质因子分解）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---