Need faster algorithm

I need to create a program which verifies if n is a perfect number or not.
I made this program, but for some reason when i submit it, i only get 90p / 100, saying the time limit is exceeded. Any help?

#include<iostream>
using namespace std;
long long n,i,s;
int main()
{
cin>>n;
s=0;
for(i=1;i<=n/2;i++)
{
if(n%i==0)
{
s=s+i;
}
}
if(s==n)
{
cout<<n<<" is a perfect number";
}
else
{
cout<<n<<" is not a perfect number";
}
return 0;
}
please use the code tag
http://www.cplusplus.com/articles/jEywvCM9/

complete edit:
one thing I'd have in mind: use int, int is the "fastes type".
Sorry, I cannot be of more help :<

an other thing that comes to my mind is that you allways recalculate the value that you want to iterate to: n/2 is computed each time
for(i=1;i<=n/2;i++)
you could store that value before looping

the next thing: ++i is a tiny tiny tiny tiny bit faster than i++ because no temporary variable has to be created.
Same goes for s=s+i; : s += i; is faster because no temporary variable has to be created
Last edited on
@Gamer2015: perfect, not prime. Has to go up to n/2.

@awkedd: you have global variables. Does it make a difference to change them to local? Does it make a difference to store the n/2 in a const?

Totally different strategy is to store all known perfect numbers in a static table and merely check if user's number is in the table ...
@Gamer2015: perfect, not prime. Has to go up to n/2.
Ohhhh yeah right, I'll edit my post
@Gamer2015: perfect, not prime. Has to go up to n/2.

The loop to the square root of n is adequate. One just has to remember that when n%i is 0, n % (n/i) is also. In other words, divisors occur in pairs. When you know that 2 goes into 6 3 times, that makes both 2 and 3 proper divisors of 6.

Of course, Gamer2015 didn't account for that in his code.
One just has to remember that when n%i is 0, n % (n/i) is also

but only count that number if n/i != i otherwise you'll count the same divisor twice

Of course, Gamer2015 didn't account for that in his code

yup
Thank you , i figured it out with your help !
Topic archived. No new replies allowed.