欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

I Older Brother(质因子分解)

程序员文章站 2022-06-07 16:53:42
...

题目
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;
            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;
}
相关标签: 数论专题