首页 > 代码库 > shu_1746 无平方因子

shu_1746 无平方因子

http://202.121.199.212/JudgeOnline/problem.php?id=1746


analy: 无平方因子数,那就是不同的素因子个数一定不超过1,于是就朝这个方向努力:

             先把2—10^9之间的所有素数求出来(也就是到99999989之间的所有素数用bool表打出来)

             然后一个一个素因子判断过去;

             再然后果断TLE了n次;

             于是,观察了一下其他人的提交记录,发现代码很短,不可能打表;时间也很短,有很好的算法?

              试后,找了一下无平方因子的相关资料,没发现很好的算法;

              于是,暴力了。。。

              然后,AC了。。。

tip: 

            用long long的n去除 int  的 (i*i) , 出现除0错(oj上,本地机倒是没有报错)

   


code:

#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
using namespace std;

int main()
{
   // freopen("in5.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int t;
    long long n;
    bool flag;
    scanf("%d",&t);

    for(int cno=1;cno<=t;cno++){
        scanf("%lld",&n);
        printf("Case %d: ",cno);

        if(n%100==0){
            printf("No\n");
            continue;
        }
        flag=false;
        for(long long i=2;i*i<=n;i++){
            if(n%(i*i)==0){
                printf("No\n");
                flag=true;
                break;
            }
        }
        if(!flag) printf("Yes\n");
    }
    return 0;
}