David W. answered • 11/24/17
Tutor
4.7
(90)
Experienced Prof
First, we must determine a more precise definition of "factors." Is it prime factors, all factors, etc.? Since the problem stated that the factors of 48 add to 124, this must mean:
1 + 2 + 3 + 4 + 6 + 8 + 12 + 16 + 24 + 48 = 124 [so, factors means all of them]
Now, "lowest number" is the result of searching several numbers. This is the way a sort program finds the lowest number, then the next lowest number, and so on. Thus, you could (a) start with a low number and stop when you find the first sum of the factors that exceeds 100 or else (b) you could start high and keep a record of the last value that had a sum of the factors that exceeded 100 (or the given number). Let's use method (a).
The core of the program will to be to find all the factors of a number (or at least keep a running sum of the factors) to determine whether it exceeds 100 (or the given number). A factor multiplied by a factor results in the number. For integers, that means that the number is evenly divisible by the factor. A very useful function in most programming languages, MOD(x,y), is the remainder function. A remainder of 0 means evenly divisible.
INPUT Given
Sum = 0 [initial value for Sum]
WHILE (Sum<=Given)
Sum = 1 [every positive integer has 1 as a factor]
FOR I = 2 TO Given [note: different syntax for different languages]
IF ( MOD(Given,I) = 0 ) THEN Sum = Sum + I [I is a factor, so add it to Sum so far]
NEXT I
END WHILE [The WHILE will stop when the Sum > Given]
David W.
Multiple considerations:
1 - larger numbers mean huge sums, so the data type (long integer?) must be able to accommodate both.
2. Now, you trade off human time vs. computer time --
I had a great discussion with a student this week. I learned computer programming using punched cards, so we did a very careful "desk check" on coding sheets before submitting the job. It would be a long time before results came back. Today, with interactive PCs. it is seconds. Also, computers are vastly cheaper and people time is significantly more expensive (the minimum wage when I started had just been increased to $1.25/hr). Most instructors fail to teach the engineering economics of computer use, but it is very important. When developing small, short programs, you may spend hours (it is also more error-prone) to save a few seconds of computer time --- why? There is value in learning the techniques, but PLZ keep them in context.
The two categories of improvements are (1) algorithmic improvements and (2) computer code improvements. For example, you may add all the numbers from 1 to 1,000.000 or you may use Gauss's formula for the sum of the numbers from 1 to N [that is, N(N+!)/2). For computer code improvements, optimizing compilers do thins like moving a static assignment statement outside a loop, computing partial results outside a loop, parallel processing, etc. Programmers often must use these techniques to improve efficiency (there are books full of these).
For this problem, the "guts" of the code takes the bulk of the time -- that is "determine the
factors of this number." Since each positive integer has prime factors, and since each factor of the number is the product of some of those primes, the program may keep an
array of primes, use only those primes that are factors, in combination, to form other factors [note: this is just one example of an efficiency improvement). Of course, no prime larger than N/2 need be considered (why?).
Prime factors of 48: 2 2 2 2 3
Factors of 48:
1
2
3
2*2
2*3
2*2*2
2*2*3
2*2*2*2
2*2*2*3
2*2*2*2*3
Report
11/25/17
Paul L.
One other question though, what if the sum given is larger, e.g. 1 million? Is there a way to make the program more efficient?
11/25/17