I Older Brother(质因子分解)
程序员文章站
2022-06-07 16:53:42
...
题目
题意: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;
else
cout<<"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);//很关键的一步,例如37
if(s.size()==1)
cout<<"yes"<<endl;
else
cout<<"no"<<endl;
return 0;
}
上一篇: 数论--质因子分解
下一篇: mysql小小笔试题_MySQL
推荐阅读
-
素数(质数)判断、打印素数表(Eratosthenes筛法)、质因子分解————附完整代码
-
CodeForces - 1114C Trailing Loves (or L'oeufs?) (质因子,阶乘分解)
-
【代码超详解】洛谷 P2043 质因子分解(分解质因数)
-
Contest100000592 - 《算法笔记》5.5小节——数学问题->质因子分解
-
口算训练(分解质因子+小思路)
-
用质因子去分解质因数
-
数论--质因子分解
-
I Older Brother(质因子分解)
-
【牛客练习44:C】小y的质数(求区间内k生互斥数对数---容斥原理+质因子分解)
-
Orac and LCM(GCD/LCM/质因子分解/推导证明)Codeforces Round #641 (Div. 2) C题