project euler problem 3

[zee2200]

alright guys i know this does somewhat defeat the point of project euler but i just do not understand this. i found a bit of code that does give you the right answer but thats not what i want. what i want to know is why does it work. heres the code that i found. the main part im confused about is how does it check if a number is prime because the algorithm does putout non prime numbers so how does it know that those numbers cant be divided evenly into the factorof. also why does it divide factor of by the number when the number is a factor?

#include <iostream>
int main()
{
	long long factorOf = (600851475143);
	int num = 2;

	while ((num * num) <= factorOf)

		if (factorOf % num == 0)
		{
			std::cout << num << std::endl;
			factorOf /= num;
		}
		else
			num++;

	std::cout << "factor is: " << factorOf << std::endl;

	system("PAUSE");

	return 0;
}

[48T7M4Gy]

I doesn't 'somewhat' defeat the purpose of Project Euler, it totally defeats the purpose, spirit, intent and wishes of Project Euler and probably spoils it for other people too.

[48bpfSEw]

The euler problem 1 has nothing to do with prime numbers as far as I understood:

https://de.wikipedia.org/wiki/Project_Euler

[48T7M4Gy]

Largest prime factor
Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

https://projecteuler.net/problem=3

[ne555]

> how does it check if a number is prime
> why does it divide factor of by the number when the number is a factor?
as you see, it never checks that `num' is a prime number, however if `num' were composite, then the test at line 9 would fail.

Suppose that num = a*b, where `a' and `b' are primes.
If `num' divided evenly `factorOf', then `a' and `b' would also do it. But `a' and `b' would be try out first and remove themselves from `factorOf', so `num' would be no longer a divisor.

The same argument can be made for `a' and `b', so line 9 would only succeed if `num' is a prime number.