Thread: Project Euler Questions

Code:

#include <stdio.h>int main(void) {
	//a != b , if d(b) = a ve d(a) = b 
	int DividedSum;
	int index;
	int temp;
	int sum=0;
	for(index = 1; index<10000; ++index)
	{
		DividedSum = DividedByZero(index); //a
		temp=DividedByZero(DividedSum);   //b
		if(DividedSum!=temp)
		{
			if(DividedByZero(temp)==DividedSum&&DividedByZero(DividedSum)==temp)
			{
			//	printf("%d ",index);
				sum +=index;
				printf("%d ",sum);	
			}
			
		}
		
	}
	printf("\n\n%d",sum);


	return 0;
}


int DividedByZero(int Number)
{
	int index;
	int sum = 0;
	for(index = 1; index < Number; ++index)
	{
		if(Number%index==0)
		{
			sum += index;
		}
	}
	return sum;
}

Program shows 63968
But answer is 31626.
Where did I make a mistake? What was the wrong ?

Ohh sory..

Link : https://projecteuler.net/problem=21

Let's get some variables straight. The variable `a' needs to be the loop counter, because you will do: b = DividedByZero(a);
then temp = DividedByZero(b);
and if b != a && temp == a, you found an amicable pair.

I think your mistake was that you started off the search using the index and never compared with the index again.

Thank you whiteflags. It runs. I understand my problems.

EDIT: Too slow!

Compile your code at maximum warning level. You will see that it complains about DividedByZero being an unknown function when you call it in main. Move your function above main to solve it.

DividedByZero is a horrible name for your function, by the way. It doesn't divide anything by zero. Instead, why not name it SumProperDivisors?

It also might help if you used the same terminology/variable names as the explanation on the Project Euler page. In your case, index is a, DividedSum (another bad name) is d(a) and temp is d_b. At least, that's the best I could figure out, your code is a bit convoluted. Let's look at your function, substituting the names used by the Project Euler page:

Code:

for (a = 1; a < 10000; ++a)
{
    d_a = SumProperDivisors(a);
    d_b = SumProperDivisors(d_a);
    if (d_a != d_b)
    {
        if (SumProperDivisors(d_b) == d_a && SumProperDivisors(d_a) == d_b)
        {
            sum += a;
            printf("%d ", sum);
        }
    }
}

That seems more complex than the Project Euler description. The outer if seems wrong and I'm not sure what the inner if is trying to do. We never actually check if a != b. Maybe it's handled in your wonky if statements, but it's hard to tell.

Try breaking it down into functions a bit more, so your main loop is something like:

Code:

for a from 1 to 10000
    if (NumHasAmicablePair(a))
    {
        sum += a;  // don't add the other number, else we will double-count it when a gets to that value
    }

Now we have to define NumHasAmicablePair. Start with some pseudo code

Code:

#include <stdbool.h>  // to use bool type -- all C99 compliant or later compilers support this; if you don't have it, just use int and return 1 (true) or 0 (false)
bool NumHasAmicablePair(int a)
    d_a = SumProperDivisors(a)
    b = d_a  // this is superfluous, since d_a == b, but it helps keep things in line with the Project Euler description
    d_b = SumProperDivisors(b)
    // we know d_a == b, since we set it above, check the other conditions
    if d_b is equal to a and a is not equal to b
        return true
    else
        return false

You could simplify the last if/else by returning the condition directly:

Code:

return d_b is equal to a and a is not equal to b;

anduril462 thank you so much. Your explanation is perfect. I gave a pencil and paper I study carefully one each, one apiece.

The code you have provided in the description didn't made sense because of several reasons.
The names. This is not a code review but the names are just too bad to not be reviewed. One programmer reviewing code will completely loose the logic by trying to figure out what does diving has to do with summation.
Also, a list of amicable numbers does not even make sense. Amicable numbers come in pairs.

The code wasn't even compilable on a first point, and the reasons are already up.
When you have found (220, 284) you need to record that you have already found 284, otherwise when the loop iterates to 284 it will find 220 again.
Crudely, with no thought given to optimisation, and in VB:

Code:

Sub

Code:

ListAmicablePairs()
    Dim alreadyFound AsNewList(OfInteger)
    For i =1To9999
        Dim spd1 =SumProperDivisors(i)
        Dim spd2 =SumProperDivisors(spd1)
        If spd2 = i AndAlso spd1 <> i AndAlsoNot alreadyFound.Contains(i)Then
            alreadyFound.Add(i)
            alreadyFound.Add(spd1)
            Console.WriteLine("({0}, {1})", i, spd1)
        EndIf
    Next

    Console.WriteLine(alreadyFound.Sum())

EndSub

Outputs:

(220, 284)
(1184, 1210)
(2620, 2924)
(5020, 5564)
(6232, 6368)
31626

When you have found (220, 284) you need to record that you have already found 284, otherwise when the loop iterates to 284 it will find 220 again.
Crudely, with no thought given to optimisation, and in VB:

You might think that is a problem but in practice it isn't. If you test 220 first, it will generate it's mate, 284. When you test 284 it will generate 220. Simply add one part of the pair to the sum when the logic works, and there won't be any missed pairs or duplicates.

Originally Posted by whiteflags

You might think that is a problem but in practice it isn't. If you test 220 first, it will generate it's mate, 284. When you test 284 it will generate 220. Simply add one part of the pair to the sum when the logic works, and there won't be any missed pairs or duplicates.

I don't think.