The algorithm I need to come up with is one that computes all the factors for a user-entered number, for example the user would enter "50" and the program would display all the factors of fifty which are: 1, 2, 5, 10, 25, 50.
This program would need to work for all positive integer values.
Would anybody be willing to show me how to do it? This is not homework, its just study material, and I have been trying to figure this out for over 2 hrs. Should I use arrays?
I think you need to give us more information. What are the requirements for your algorithm? Does it have to have a particularly good running time? What functions do you have access to?
If there are no restrictions, I would say just loop through integers x less than the input and check if input / x is an integer, if so then x is a factor.
Here's a clue: a number X is a factor of Y if Y / X does not have a remainder. Another clue: there are common mathematical operators in most languages to discover if one number divided by another has a remainder.
The naive algorithm is to try to divide (or check the remainder) the input number n by all numbers less than Math.Sqrt(n) + 0.5. This is fine for studying.
So, in pseudocode:
integer n from user input
for each integer i in the range 1 to sqrt(n) + 1/2 do
r = remainder of n divided by i
if r is zero print i and n/i
First, try a naive / brute-force approach.
For example you could iterate through all numbers between 1 and the [hopefully relatively small] number supplied by the user, and check if it divides, evenly, this number.
BTW, you can use the modulo operator to assert the fact that a given integer is exactly divisible by another integer (or more precisely the result of the modulo operation should be a particular value).
Once you have this working you can think of the ways that some of the numbers in the iteration could be eliminated. This approach is not unusual in solving problems:
1) solve the problem in a naive fashion and
2) look for ways to cut/filter/prune and otherwise improve upon the naive approach.
If nothing else, the naive approach provides a good baseline, and, because it is also simpler, it can also be used to verify the output of more complicated approaches.
Once you have played enough with this solution, you may try a distinct approach. The idea would be to decompose the number into its prime factors. In the example, 50 would give (1, 2, 5, 5, 50), and then you'd need to enumerate all the combinations of these prime factors (excluding the trivial, 1 and 50). The prime factor decomposition should generally be straight forward (think of the way you learned it in earlier math classes), but the enumeration of all possible combination may cause you to pause a bit (this is however the type of algorithms that keep coming in a fashion or another in CS applications).
I might go for the more simple .NET version:
int factor = 3447; // Input
List<int> results = new List<int>();
for (int i=1; i<factor; i++) {
for (int j=1; j<factor; j++) {
if ( i % j == 0 ) {
results.Add(i);
break;
}
}
}
That should yield the expected results. It works by incrementally going through all numbers from 1 to X (the number to factor). The inner loop goes through the same set of numbers to see if the modulus is zero (no remainder). Once one is found we move on because otherwise we would get duplicates.
Also note that this is a worst-case scenario (brute force) algorithm.
I assume you've written the program, but w/e.
% operator is your friend here.
x % y = 0 if and only if x is divisible by y (meaning no remainder, meaning y is a factor of x).
In C#, to get the factors of 50, the following operation must be true:
if(50 % x == 0)
Console.WriteLine(x + " is a factor of 50");
Here is a brute way of getting the factors of 50 from 1 to 100:
int toTest = 50;
for(int x = 1; x < toTest; x++)
{
if(toTest % x == 0)
Console.WriteLine(x + " is a factor of 50");
}