Weirdly Behaving For Loop

[Jack41EL]

Here is a snippet of code from my attempt to solve a problem from Project Euler. I expected the snippet to output the factors of 600851475143, but the function outputs the first factor, and then it outputs numbers that keep doubling starting at 128 and ending at 524288. Can someone tell me why this happens, and what I can do to fix this?

#include <iostream>
#include <cstdint>


void greatestPrimeFactor(uint64_t inputNumber)
{
	uint64_t greatestFactor;
	int factorCount = 0;
	uint64_t *listPtr = &greatestFactor + 1;
	
	for (unsigned int currentDivisor = 2; currentDivisor <= sqrt(inputNumber); currentDivisor++)
	{
		if (inputNumber % currentDivisor == 0)
		{
			factorCount++;
			*(listPtr + factorCount) = currentDivisor;
			std::cout << currentDivisor << std::endl;
		}
	}}


int main()
{
	greatestPrimeFactor(600851475143);
	return 0;
}

[kbw]

Seems fine to me:

#include <list>
#include <math.h>

//typedef unsigned long long uint64_t;
typedef std::list<uint64_t> vec_t;


void greatestPrimeFactor(vec_t& factors, uint64_t inputNumber)
{
	for (uint64_t currentDivisor = 2, mx = sqrt((long double)inputNumber); currentDivisor <= mx; ++currentDivisor)
	{
		if (inputNumber % currentDivisor == 0)
		{
			factors.push_back(currentDivisor);
		}
	}
}


int main()
{
	vec_t factors;
	greatestPrimeFactor(factors, 600851475143);
	return 0;
}

[Jack41EL]

Thanks for the solution! Can someone explain why my code won't work?

[nickeeromo]

I am also kind of a beginner, but your code is not easy to follow. You have foreign data types to me with pointer addition, etc., but here is my two cents.

greatestFactor is not initialized, but not sure if that is relevant. listPtr is of type uint64_t, while factorCount is of type int, and currentDivisor is a third type, unsigned int. In your pointer addition piece,

*(listPtr + factorCount) = currentDivisor;

you have them all trying to work together, but that shouldn't simply affect the value OF currentDivisor (which is the only outuput). Should it?

You are also using the sqrt function, but that should be found in a math header, not in iostream or cstdint, but I'm sure that would just give you a syntax error, so you probably just left that out by mistake here.

OK so I just ran it myself to see the actual output, and it wouldn't compile without first including cmath and then doing what kbw has to convert the type inside the sqrt function to long double. However, since that type is not the same, something erroneous may be happening, but AGAIN this has nothing to do with the value of currentDivisor...

Your problem SEEMS systematic in that the numbers are doubling, so it may be something simple we are missing. And of course, 128 would obviously be wrong as a factor because since the original number is odd, 8 will never go into it.

If it were me, for simplicity, I would probably get rid of the pointer stuff and make them all the same data type (a more simple type) for testing, then edge my way into the more advanced stuff from there, probably starting with the additional data types first. Hope I have been helpful.

[kbw]

Can someone explain why my code won't work?

You'll need to show where listPtr is declared and where you print its content as you loose the array size.

Also,

listPtr[factorCount] = currentDivisor;

is a much nicer coding of

*(listPtr + factorCount) = currentDivisor;

[dhayden]

uint64_t greatestFactor;
uint64_t *listPtr = &greatestFactor + 1;
...
*(listPtr + factorCount) = currentDivisor;

You are treating listPtr like it points to an array, but it doesn't. In fact, you initialize it to the address after greatestFactor, which could be anything at all. As a result your program has undefined behavior.

Neither your solution nor kbw's will find the largest prime factor since it can be greater than sqrt(n). For example, the largest prime factor of 26 is 13. Here is a version that is faster and will find all prime factors of a number:

void greatestPrimeFactor(uint64_t inputNumber)
{
    for (uint64_t currentDivisor = 2; inputNumber > 1;) {
	if (inputNumber % currentDivisor == 0) {
	    std::cout << currentDivisor << ' ';
	    inputNumber /= currentDivisor;
	} else {
	    ++currentDivisor;
	}
    }
    std::cout << '\n';
}