Why isn't this working?

This is a discussion on Why isn't this working? within the C Programming forums, part of the General Programming Boards category; Hi guys, I wrote up a long program that pretty much works. What it does is when the user enters ...

  1. #1
    Registered User
    Join Date
    Mar 2011
    Posts
    22

    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.
    Last edited by Watabou; 04-21-2011 at 12:09 AM. Reason: changed sumdivisors.

  2. #2
    Registered User
    Join Date
    Mar 2011
    Posts
    261
    I don't know what an amicable number is (sorry didn't look it up...)

    Code:
    	
    for (i = 1; i <= number; i++) {
            for (j = 1; j >= number; j--) {
    ...

    The 'j' loop seems to never fire unless number is negative? but then the 'i' loop won't in that case. Is this what you want?

  3. #3
    Registered User
    Join Date
    Apr 2011
    Location
    Las Vegas
    Posts
    66
    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

  4. #4
    Registered User
    Join Date
    Mar 2011
    Posts
    22
    Quote Originally Posted by kmess View Post
    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?
    Last edited by Watabou; 04-20-2011 at 10:05 PM.

  5. #5
    Registered User
    Join Date
    Apr 2011
    Location
    Las Vegas
    Posts
    66
    No worries - I understand amicable numbers. That's probably the only reason I caught the sumDiv() issue. :P

    Standing by...

    Kevin

  6. #6
    Registered User
    Join Date
    Apr 2011
    Location
    Las Vegas
    Posts
    66
    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
    Last edited by kmess; 04-21-2011 at 12:02 AM.

  7. #7
    Registered User
    Join Date
    Mar 2011
    Posts
    22
    Yeah you're right. I was actually planning on doing that later. It's what I used for prime and perfect numbers. I wanted to see what the program was actually doing in the debugger so I thought it would help having 1 to n here.

  8. #8
    Registered User
    Join Date
    Apr 2011
    Location
    Las Vegas
    Posts
    66
    So, as for your findAmicable() function, let me draw your attention to something else. In theory, you're looking for all the amicable numbers in a range of 1 to whatever. So, we know you're going to have at least one loop. I would propose to you that you only need the one loop instead of two.

    Let's say you have a number, n, and you want to find out if it is part of an amicable pair.

    First, you need to know the sum of its factors, which you'll find from sumDiv(). You'll want to save this sum for later.
    Code:
    int sum1 = sumDiv(n);
    Next, we want to start looking for another number that is the other half of an amicable pair. The most direct thing to do is to simply find the sum of factors of sum1 from above. If it is the same as n (the value we started with), we have our amicable pair!

    Code:
    if (sumDiv(sum1) == n) ...
    If not, continue with the next iteration of the loop (and the next value of n).

    See if that makes sense. If you can get this part working, then you can refine the code next.

    Kevin

  9. #9
    Registered User
    Join Date
    Apr 2011
    Location
    Las Vegas
    Posts
    66
    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).
    Last edited by kmess; 04-20-2011 at 11:48 PM.

  10. #10
    Registered User
    Join Date
    Mar 2011
    Posts
    22
    Okay I'm a bit confused now.

    So first I get all the factors of n and sum it. And that's sum1.

    Then I make a loop to find the second number to go with it? How would I do that? Won't that be a infinite loop since it needs to check numbers greater than n?

  11. #11
    Registered User
    Join Date
    Apr 2011
    Location
    Las Vegas
    Posts
    66
    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
    Last edited by kmess; 04-21-2011 at 12:10 AM. Reason: Correct pseudocode

  12. #12
    Registered User
    Join Date
    Mar 2011
    Posts
    22
    Hmm okay so this is what I think you're saying:

    Code:
    void findAmicable(int number) { 
    	 int sum1 = sumDiv(number); 		
    	
    	if (sumDiv(sum1) == number) {
    		printf("%d %d\n", number, sum1);
    	}
    	
    }
    I mean it looks right. If I pass it 220, then sum 1 is 284. And the sumDiv of sum1 is 220 and when sumDiv(sim1) == 220 == number which is also 220, it should return it. But....it's not.

    Every time I enter 0,300, it's giving me 0 1 and 1 1 for some reason.

    That means my sumDiv method isn't correct?

  13. #13
    Registered User
    Join Date
    Apr 2011
    Location
    Las Vegas
    Posts
    66
    Can you post your sumDiv() function again?

  14. #14
    Registered User
    Join Date
    Mar 2011
    Posts
    22
    Yeah it's this:

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

  15. #15
    Registered User
    Join Date
    Apr 2011
    Location
    Las Vegas
    Posts
    66
    That looks good as did your findAmicable() function. Can you show me how you're calling this (the loop), please?

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 9
    Last Post: 03-30-2009, 04:09 AM
  2. cin.get() Not working
    By fhbwghads in forum C++ Programming
    Replies: 3
    Last Post: 11-29-2008, 09:15 AM
  3. Working up to an FFT
    By lordbubonicus in forum C Programming
    Replies: 14
    Last Post: 12-06-2007, 08:59 PM
  4. Min Max not working
    By B0bDole in forum C Programming
    Replies: 5
    Last Post: 06-10-2005, 10:58 PM
  5. working out...
    By TechWins in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 04-10-2003, 10:20 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21