Find The Good Number :
Code :
#include
#include
int isSquareFree(int n)
{
int i;
for(i=2; i<=n; i++)
if(n%i==0)
if(n%(i*i)==0)
return 0;
return 1;
}
int isPrime(int n)
{
int i;
if(n<=1)
return 0;
else if(n==2)
return 1;
for(i=2; i<=sqrt(n)+1; i++)
if(n%i==0)
return 0;
return 1;
}
int main()
{
int low, high, s=0,sum=0, c=0, i, n, T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&low,&high);
for(n=low; n<=high; n++)
{
if(isSquareFree(n)==1)
{
s=0, c=0;
for(i=1; i<=n; i++)
if(n%i==0)
s=s+i;
for(i=2; i
if(s%i==0)
if(isPrime(i)==1)
c++;
if(isPrime(c)==1)
sum=sum+s;
}
}
printf("%d\n",sum);
sum=0;
}
return 0;
}
Explanation
- Following number in the range 1 to 10 are square free numbers : 1, 2, 3, 5, 6, 7, 10.
- Sum of their divisors will be 1, 3, 4, 6, 12, 8, 18 respectively.
- Number of prime divisors of their sum of divisors will be 0, 1, 1, 2, 2, 1, 2 respectively.
- So, the number 5, 6, 10 are good numbers