ALIQUOT SUM problem

[pokolas]

I am calculating if the number is perfect, abundant or deficient. Program works but if i enter bigger number it doesnt. Program should work with number between 1 and 10^14

  #include <iostream>

using namespace std;

int main()
{ int n;
int sum=0;
cin>>n;
for(int i=1;i<n;i++)
if (n / i * i == n){
sum+=i;
}
if (sum<n){
cout<<"deficient"<<endl;}
else if (sum>n){
cout<<"abundant"<<endl;}
else{
cout<<"perfect"<<endl;}

return 0;
}

[Handy Andy]

Hello pokolas,

The first thing I would look int is if an "int" can hold a number that is 10^14. My first thought is no.

You could try changing the "int" to a "long" or "long long" and see what happens. Meanwhile I will have to find what I want to show you. It is a small program the prints out the size of variables and the maximum number that they can hold.

Hope that helps for now,

Andy

[pokolas]

Long long doesn't help, still the same problem, i researched different data types but i think none of them can hold number of 10^14

[Handy Andy]

Hello pokolas,

I am sorry if I was not clear I meant that all variables should be "long long"s including "i" in the for loop.

The "long long" will hold 10^14 which I believe is 100,000,000,000,000. At least the calculator that comes with Windows gave me this number.

When working properly it will take awhile for the program and for loop to run. Still waiting for an answer. I will let you know when it finishes.

Hope that helps,

Andy

[lastchance]

pokolas wrote:

Long long doesn't help, still the same problem, i researched different data types but i think none of them can hold number of 10^14

Look a bit harder, @pokolas. Try running the code below on your machine.
Unsigned long long should do the trick. Remember that ALL your potentially-large integer values should have that type.

#include <iostream>
#include <limits>
using namespace std;

int main()
{
   cout << "Maximum size of unsigned short:    " << numeric_limits<unsigned short    >::max() << endl;
   cout << "Maximum size of short:             " << numeric_limits<         short    >::max() << endl;
   cout << "Minimum size of short:             " << numeric_limits<         short    >::min() << endl;
   cout << endl;
   cout << "Maximum size of unsigned int:      " << numeric_limits<unsigned int      >::max() << endl;
   cout << "Maximum size of int:               " << numeric_limits<         int      >::max() << endl;
   cout << "Minimum size of int:               " << numeric_limits<         int      >::min() << endl;
   cout << endl;
   cout << "Maximum size of unsigned long:     " << numeric_limits<unsigned long     >::max() << endl;
   cout << "Maximum size of long:              " << numeric_limits<         long     >::max() << endl;
   cout << "Minimum size of long:              " << numeric_limits<         long     >::min() << endl;
   cout << endl;
   cout << "Maximum size of unsigned long long:" << numeric_limits<unsigned long long>::max() << endl;
   cout << "Maximum size of long long:         " << numeric_limits<         long long>::max() << endl;
   cout << "Minimum size of long long:         " << numeric_limits<         long long>::min() << endl;
   cout << endl;
   cout << "Maximum size of size_t:            " << numeric_limits<         size_t   >::max() << endl;
   cout << endl;
   cout << "Maximum size of float:             " << numeric_limits<         float    >::max() << endl;
   cout << "Minimum size of float:             " << numeric_limits<         float    >::min() << endl;
   cout << endl;
   cout << "Maximum size of double:            " << numeric_limits<         double   >::max() << endl;
   cout << "Minimum size of double:            " << numeric_limits<         double   >::min() << endl;
}

When you have done that, note the following.

Your test for a factor should be
if ( n % i == 0 )

You only have to test up to sqrt( n ), since i is a factor of n if and only if n/i is also a factor. This will reduce your large problem by a factor of ... 10 million. Worth it?
Then sum += i + n / i; except for the two following special cases:
> i=1 is a proper factor of n>1, but its pair is n itself, which is a factor, but not a proper factor, so shouldn't be added to the sum.
> If n is a perfect square then i and n/i will be the same if i=sqrt(n) and shouldn't be double-counted.


This is what I get for 10¹⁴:

Sum of proper factors is 149992370597277
100000000000000 is abundant

[Handy Andy]

Hello pokolas,

After 4 1/2+ hours of letting your program I finally gave up. It looks like lastchance has the better approach although I have not quite figured it all out yet.

It looks like your program is doing something just not quite what it should.

Andy