Largest Prime Factor

[football52]

I know this code is not finished, I'm just completely lost on where I go from here. When I debug it. Even if the number isn't prime it adds it to the largest number

  int main()
{
	long long int num = 600851475143;
	int largest = 0;

	for (int factor = 1; factor < num; factor++)
	{
		
		
		if (!(factor%num) == 0)
		{
			largest = factor;
		}
	}

	cout << largest << endl;
	return 0;
}

[football52]

Bump

[Chervil]

1. To test whether factor is a factor of num, test the remainder given by num % factor. You have it the other way around.

2. 1 is not a prime number, so you should start the loop from 2.

3. Project Euler problems usually require some creativity in order to overcome some pitfall or other. In this case the main issue is the large size of the value 600851475143, which means testing all factors up to 1 less than that value could take an infeasibly long time.

[football52]

Alright I changed it around, but its still when I run the debugger, every value enters the if statement. Am I missing something?

int main()
{
	long long int num = 600851475143;
	int largest = 0;

	for (int factor = 2; factor < num; factor++)
	{
		
		
		if (!(num%factor) == 0)
		{
			largest = factor;
		}
	}

	cout << largest << endl;
	return 0;
}

[Hiten]

On line 10 try if(!(num%factor))

[football52]

just did that and now its entering numbers and giving me an output for smaller numbers like if
num = 8676;

but if I were to put in the 600 billion, it opens the console window and its blank and I let it run for 3 minutes before the program stopped working. I want don't want to just choose a lower the num value because yes it is for project eueler but I want to know how to fix this problem if it were to occur again.

Also, if I enter the number 8756 it gives me 4378 which is not a prime number

[football52]

Bump

[Chervil]

I don't see anywhere in the program that you test whether or not the factor is prime. This factor++ simply generates consecutive integers.

You could of course add some extra code to test whether or not each factor is prime, that would work, but would also make the program run even more slowly. There are other possibilities which render that unnecessary.

Think about how you can reduce the number of iterations of the loop.
For example, say we have
num = 48
the prime factors are: 2 2 2 2 3
Is it necessary to test every factor from 2 to 47?

Or another example:
num = 8764
the prime factors are: 2 2 7 313
again, do you really need to test every factor from 2 to 8763?

Whenever you find a factor you can use that known fact in order to reduce the number or iterations required. Another possible way of reducing the required number of iterations is to test factors which are no larger than the square root of the number.

[Chervil]

There's an awful lot of bumping going on around here. Patience, grasshopper.

[football52]

Just trying to keep it on the first page lol threads get pushed back pretty quick in the beginner forum

[Chervil]

You're too lazy to look on the next page(s) for a reply? Don't forget that there are other users whose questions are important to them too. I'm tempted to not post any further replies at all.

[football52]

Its not that Im lazy, I havent been around long enough to know how active this forum is compaired to others. Ive experienced other forums where if your post goes on the second page it will never be answered because most people only look at recent stuff.

Its not that im saying my pos is more important than everybody elses, they all have the same importance, its just me being unaware how axtive this forum is

[giblit]

Doing project euler I see. Well I will advocate using a sieve for the primes but in this case I can tell you it is a VERY _small number and even if you brute forced you'd have it done in a matter of seconds. If you don't even care about finding if a number is prime off the start you could iterate and dive while possible until it has a value of 1. Then look at the numbers there divided in and see which is a prime and the largest.

Something like this (without a sieve)

for(int i = 3; number > 1; i += 2) //its odd so no need to check evens
{
    if(number % i == 0) factors.push_back(i); //or use a set and put in while loop
    while(number % i == 0)
    {
        number /= i;
    }
}

//you now have the factors. 

The sieve way would be to generate primes like:

std::vector<bool> sieve(sqrt(number)+1, true);
//the evens can stay true who cares
//if you want you can do math so the sieve only contains
//odds but I have to leave soon so won't do that
for(int i = 3; i <= cbrt(number); i += 2)
{
    if(sieve.at(i))
    {
        for(int j = i*i; j <= number; j += i)
        {
            sieve.at(j) = false;
        }
    }
}

//check if it is even first
for(int i = 3; i <= sqrt; i += 2)
{
    if(sieve.at(i) && number % i == 0) factors.push_back(i);
}

//have a list of prime factors. The largest will be the back one
//you could also do the divide method and break when it is == 1 

*Added emphasis