C++ Abundant Number ProgramDate: 01/26/2001 at 04:21:05 From: Amaka Agbor Subject: C++ Abundant Number Program Is there some computer science C++ formula that allows the user to check if a number is abundant, deficient, or perfect? I have to write an interactive program that allows the user to enter a positive integer, find the sum of the integer, and print if it is abundant, deficient or perfect... Date: 01/26/2001 at 14:02:24 From: Doctor Schwa Subject: Re: C++ Abundant Number Program Yes, there is a formula to find the sum of the factors. There are a few different ways you could do it. One way, easier to understand but perhaps slower to execute, is something like this, assuming that "n" is the number that your user enters: total = 0 for (low = 1, high = n ; low <= high ; low++, high = n/low) if (n % low == 0) total = total + low + high; What that does, for a number like 30 let's say, is start with low = 1, high = 30, so total now = 31 low = 2, high = 15, so total now = 48 low = 3, high = 10, so total now = 61 low = 4, high = 7, but total doesn't change low = 5, high = 6, so total now = 72 low = 6, high = 5, so the for loop is done. There is at least one bug in my program; try it for a number like 9 and the bug I'm thinking of should become apparent. I'll leave it to you to fix that bug and check whether there are any others. Another possible method, which will usually be a lot faster for big numbers, first produces the prime factorization of the number. Suppose you already have the prime factorization, so prime[i] is the ith prime number, and exponent[i] is the exponent that it's raised to, so for our example of 30, the prime array has 2,3,5 in it and the exponents are 1,1,1 since 30 = 2^1 * 3^1 * 5^1. I'll say "last" = 3, since there are 3 different primes in the list. If you have that, then a clever shortcut for finding the sum of the factors of a number is as follows: total = 1 for (i = 0 ; i < last ; i++) { for (j = 0, sum = 0 ; j < exponent[i] ; j++) { sum = sum * prime[i] + 1; } total *= sum; } Now for our example of 30, sum = 1, sum = 3, and then total = 3; sum = 1, sum = 4; and then total = 12; sum = 1, sum = 6, and then total = 72. Magic? Well, if you try distributing (1 + 2) (1 + 3) (1 + 5), you'll see all the factors of 30 appear. Similarly, if you distribute (1 + 2 + 2^2 + 2^3)(1 + 3 + 3^2), you'll find all the factors of 2^3 * 3^2 = 72 in that list. I hope at least one of those algorithms makes sense to you. If not, please write us back for some clarification. Have fun, - Doctor Schwa, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/