1180 - Perfect Numbers

[uDebug]

On this problem, note that the integers on the second line are separated by commas - and not spaces.

[Shahidul.CSE]

Code: Select all

cut

[lighted]

Why do you think that p is one digit number? It can be greater than 9.

Code: Select all

p=num[i]-'0';
n=pow(2,p-1)*(pow(2,p)-1);

This problem is tricky. I checked that p can be greater than 1000.
So you can forget about checking if sum of proper divisors are equal to a number.
And you don't need to check it.

Think about this condition

Euclid proved that an even number is perfect if it has the form
2^(p-1) * (2^p - 1)
where both p and 2^p - 1 are prime numbers.

And this condition

The largest perfect number in this problem will not exceed 2^33

By the way i read p this way

Code: Select all

scanf("%d", &t);

while (t--) {

  scanf("%d", &p);

  if (t) scanf(" %c", &c);

  ..
}

[Shahidul.CSE]

Code: Select all

cut

[lighted]

If max value of perfect number is 2^33.

Then 2^(p-1) * (2^p - 1) <= 2^33. Can you get max value for p?

If given p is greater than max value i print "No" because they will be not perfect numbers according to problem description.

[Shahidul.CSE]

Code: Select all

cut

[lighted]

Your prime checking is wrong.
When you solve problems relating to prime numbers -> Add a condition that 1 is not a prime.
(if problem description didn't said anything about it)

It would be better if you make function isPrime(int n) that checks if number is prime.

[Helaluddin_brur]

getting TL

any suggestion ?

here is my code

Code: Select all

#include<stdio.h>
#include<math.h>
int main()
{
    unsigned long long int n,i,j,p,sum,t;
    //freopen("1180.txt","r",stdin);
    while(scanf("%llu",&t)==1)
    {
        for(i=0;i<t;i++)
        {
            scanf("%llu",&p);
            if(i<t-1)
                scanf(",");
            sum=0,n=0;
            n=pow((double)2,p-1)*(pow((double)2,p)-1);
            for(j=1;j<n;j++)
            {
                if(n%j==0)
                    sum+=j;
            }
            if(n==sum)
                printf("Yes\n");
            else
                printf("No\n");
        }

    }
    return 0;

}

[Shahidul.CSE]

Helaluddin_brur,
According to your code, you should print Yes, when both f and f1 is 0.

[lighted]

Doesn't match sample I/O. Input numbers are separated by commas(','). You should read this commas from standart input.

[ssavi]

Why I am getting TLE ?? Please Help ....

Code: Select all

#include<stdio.h>
#include<math.h>
int main()
{
    long long int n, i, p, a[100000], j, d, sum;
    char ch;
    while(scanf("%lld",&n)==1)
    {
        for(i=1;i<=n;i++)
            {
               scanf("%lld,",&a[i]);
               scanf("%c",&ch);
            }
       for(i=1;i<=n;i++)
       {
           d = (pow(2,a[i]-1))*(pow(2,a[i])-1);
           sum=0;
           for(j=1;j<d;j++)
           {
               if((d%j)==0)
                  sum = sum+j;
           }
           if(sum==d)
            printf("Yes\n");
           else
            printf("No\n");
       }
    }
    return 0;
}

[brianfry713]

http://en.wikipedia.org/wiki/List_of_perfect_numbers

[lighted]

ssavi, if you want to optimize your code read posts in this thread.