Sphenic numbers质因数分解-白红宇

Sphenic numbers质因数分解

阅读量：4204 次

发布时间：2019-05-26

本文共 904 字，大约阅读时间需要 3 分钟。

https://odzkskevi.qnssl.com/415c275cb0a15fcb4ede21b8cb5297de?v=1488850248

2016-2017 ACM中部地区的俄罗斯四分之一决赛编程比赛

G.施尼希数

小学生瓦西亚对区分素数的问题感兴趣。他

已决定开发自己的测试方法。

不幸的是，新算法有一个缺陷 - 它产生假阳性输出

在具有所谓的蝶形数的情况下。对于那些不知道的人：sphenic

数字是三个不同质数的乘积。

帮助Vasya写一个程序来区分sphenic数字。

Inut

输入文件包含单个数字 - 整数n。

限制

30≤n≤10467397。

输出

输出文件必须包含一行具有值“YES”（不带引号）的行

标记），如果数字n是罗真的，或者如果不是，则为“否”。

例子

Input.txt Output.txt

30 YES

40 NO

10467397 YES

#include
   
    #include 
    
     #include 
     
      #include 
      
       #define ll long long#define maxn 10467397using namespace std;int get_num(int n){    int cnt=0;    for(int i=2;i<=sqrt((double)n);i++)    {        if(n%i==0) cnt++;        while(n%i==0)        {            n=n/i;        }    }    if(n>1) cnt++;    return cnt++;}int main(){    freopen("input.txt","r",stdin);    freopen("output.txt","w",stdout);    int n;    while(cin>>n)    {       int flag=get_num(n);       if(flag==3)cout<<"YES"<