Thread: Why isn't this working?

Hi guys, I wrote up a long program that pretty much works. What it does is when the user enters a string like 4,100 the program prints out all the prime,perfect and amicable pairs in that range.

Trouble is, I got the prime and perfect numbers to work but I'm having a bit of difficulty getting the amicable pairs.

Here is part of the code in main where the numbers from the user gets passed to the findAmicable method.

Code:

while (1) {
		
		printf("Enter a command: ");
		
		fgets(command, sizeof(command), stdin);
		command[strlen(command) - 1] = '\0';
		
		if (sscanf(command, "%d,%d", &A, &B) == 2) {
			int i;
			for (i = A; i < B; i++) {	
					   findAmicable(i);
                        }
                 }
}

And here is the sum of the factors method and the findAmicable methods:

Code:

int sumDiv(int number) {

	int i;
	int sum = 0;	
	for (i = 1; i <= number; i++) {
              if(number % i == 0) 
		sum += i;
	}
	return sum;
}

void findAmicable (int number) {
	int i;
	int j;
	for (i = 1; i <= number; i++) {
		for (j = 1; j >= number; j--) {
			if ((sumDiv(i) == j) && (sumDiv(j) == i) &&(i!=j)) {
				printf("%d and %d are amicable numbers. \n", i, j);
			}
		}
	}
}

Help please? I don't know where the code is wrong.

Originally Posted by kmess

Hi Watabou. Looking at your sum of factors (sumDiv), it appears to be more of a sum of numbers. Somewhere in that function, shouldn't you determine if a value is a factor of "number" before you add it to the sum?

Kevin

Oh whoops, maybe that's the problem. I'll see if that fixes it.

Oh and it's kinda hard to explain amicable numbers. One example is 220 and 284. They are amicable numbers since the factors of 220 add up to 284 and the factors of 284 add up to 220. So they form a pair.


I know there should be a better algorithm than what I'm doing. I've looked over some Euler's algorithms but that's confusing...

EDIT: Hmm, I changed the sumDiv method but it still won't work.
EDIT: Oh wait, what mike said makes sense. At first, I had it so that it accepted two parameters and I had to change it to one since the program guidelines state that.

I had the end point as the starting point for j so that's why it doesn't work as of now....
But then what can I do now?

I looked more closely at your code, Watabou. You are testing for even divisibility (missed it in my haste) -- but here's a hint - you don't want to iterate from 1 to n. Let's take a look at a random number, say 220. The factors of 220 are 1,2,4,5,10,11,20,22,44,55, and 110. The sum of these is 284, which is the value we're expecting. Note that there is no reason to exceed n/2 in the loop (in fact, you don't need to exceed the square root of n, but there's another trick in that).

Kevin

PS. I'm building this along with you as we talk about it. The results I have for 1..n..5000 are:

Code:

$ ./a.out 
(6, 6)
(28, 28)
(220, 284)
(284, 220)
(496, 496)
(1184, 1210)
(1210, 1184)
(2620, 2924)
(2924, 2620)

The refining I'm referring to is the elimination of reciprocal pairs (e.g. 220,284 and 284,220) and perfect numbers (e.g. 6 and 28).

No, you don't want a loop. Remember an amicable pair has the same sum of factors. Consider 220,284:

Code:

sumDiv(220) == 284, AND 
sumDiv(284) == 220

If we find the sum of factors for a number, we need only compare that sum to the original number to see if it is an amicable pair (actually, without a little refining, we also get perfect numbers in the mix, but more on that later).

Pseudocode so far:

Code:

for n in range(1..5000) do:
    sum1 = sumDiv(n);
    if sumDiv(sum1) == n:
        We have two numbers whose sum of factors is equal!

So, if n = 220, sum1 = sumDiv(220) , which is 284. sumDiv(sum1) = sumDiv(284) = 220, which is the original value of n. We have an amicable pair.

Kevin