文章

28

粉丝

230

获赞

23

访问

241.9k

头像
75%的原因:如果本身是质数就要单独处理,否则就会超时
P1156 清华大学上机题
发布于2021年3月10日 20:42
阅读数 9.4k

#include <iostream>
#include <math.h>

using namespace std;
int FindBigX(int x,int y);
int judge(int Num);
int main(int argc, char const *argv[])
{
    int N,count;
    while(cin>>N)
    {
        count=0;
        int i=2;
        if (judge(N))
        {
            count=1;;
            N=1;
        }
        while(N != 1)
        {
            if (N%i==0)
            {
                N=N/i;
                count++;
            }
            else
            {
                i=FindBigX(i,sqrt(N));
            }
        }
        cout<<count<<endl;
    }
    return 0;
}

int FindBigX(int x,int y)
{
    for (int i = x+1; i <=y; ++i)
    {
        if (judge(i))
        {
            return i;
        }
    }
}

int judge(int Num)
{
    for (int j = 2; j < sqrt(Num); ++j)
    {
        if (Num % j == 0)//一旦发现存在因子则返回0(不是素数)
        {
            return 0;
        }
    }
    return 1;
}
...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发