2015
04-13

# Squarefree number

In mathematics, a squarefree number is one which is divisible by no perfect squares, except 1. For example, 10 is square-free but 18 is not, as it is divisible by 9 = 3^2. Now you need to determine whether an integer is squarefree or not.

The first line contains an integer T indicating the number of test cases.
For each test case, there is a single line contains an integer N.

Technical Specification

1. 1 <= T <= 20
2. 2 <= N <= 10^18

The first line contains an integer T indicating the number of test cases.
For each test case, there is a single line contains an integer N.

Technical Specification

1. 1 <= T <= 20
2. 2 <= N <= 10^18

2
30
75

Case 1: Yes
Case 2: No

#include<stdio.h>
#include<math.h>
#include<string.h>
#define M 1100000
#define MIN 0.00001
int a[M],b[500000],flag;
int init()
{
int i,j;
memset(a,0,sizeof(a));
for(i=2;i*i<=M;i++)
{
if(!a[i])
{
for(j=i*2;j<=M;j=j+i)
{
a[j]=1;
}
}
}
j=1;
for(i=2;i<=M;i++)
{
if(!a[i])

{
b[j]=i;
j++;
}
}
return j;

}
void pd(double nu)
{
double a;
a=sqrt(nu);
if(a-floor(a)<=MIN)
flag=0;
else
flag=1;

}
int main()
{
int n;
scanf("%d",&n);
int cs=0;
int len=init();
//printf("%d\n",len);
while(n--)
{
cs++;
__int64 num;
int i;
scanf("%I64d",&num);
flag=0;
for(i=1;i<len;i++)
{

int sum=0;
while(num%b[i]==0)
{
num/=b[i];
sum++;
}
if(sum>=2)
{
flag=1;
break;
}
}
if(flag==1)
{printf("Case %d: No\n",cs);continue;}
if(num==1)
{printf("Case %d: Yes\n",cs);continue;}
pd((double)num);
if(flag==0)
printf("Case %d: No\n",cs);
else
printf("Case %d: Yes\n",cs);
}
return 0;
}


1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术，也不懂什么是算法，从而也不要求程序员懂什么算法，做程序从来不考虑性能问题，只要页面能显示出来就是好程序，这是国内的现状，很无奈。