Vector of prime factors/Using large numbers?

[ECEsasha]

Hi! I'm playing around with vectors and Project Euler and I can't seem to figure out why this code won't work. I'm trying to make a vector of all the prime factors of 600851475143 and print the last entry. It compiles successfully, but when I run the executable file, it stops working after several seconds. Is it just timing out because 600851475143 is a large number? If so, what can I do about that?

#include <iostream>
#include <vector>

using namespace std;	


int main(){

	vector<int> primes;

	for(int i = 2; i<=600851475143; i++){	/* iterates from 2...600851475143 */
											/* 'i' is the actual number to be stored in vector */
		for(int j = 2; j <= 600851475143; j++ ){	/* For every integer between 2 and 600851475143, we see if 600851475143 is divisible by it. */

			if(600851475143%j == 0){	/* If  it is divisible by one of these numbers, we now know it is a factor of 600851475143. So we see if it is prime! */
				int tick = 0;	/* resets tick to 0 */
				for(int k = 2; k<= i; k++){	/* for all integers 2...i */
					if(i%k == 0){	/* if it is divisible by anything from 2...i, we make a tally of it */
						tick++;	/* adds a tally */
					}
				}
				if(tick == 0){	/* if the tally is still 0, we add i to our vector! */
					primes.push_back(i);
				}
			}
		}
	}

	cout << primes.back() << '\n';	/* prints the last entry of the vector, primes */

	return 0;
}

[Cody0023]

I'm guessing 600 billion is out of range for an int data type. You're gonna have an overflow and variable i will just wrap around into the negatives. Even if you used a double your program will iterate a septillion amount of times. I think this would take too long for project euler to accept as an answer.

[ECEsasha]

I replaced every int with long long int and ran my code. It's still running and hasn't timed out yet. The website said it shouldn't take more than a minute to run, though.

I'm not really sure how to handle large numbers. Any tips?

[giblit]

You should consider using a sieve to find primes. Though this number has a very small prime factor(less than 10,000) so you could just brute force it like you are doing now but with a smaller upper limit. Though I wouldn't suggest since if you continue doing project euler you will have a VERY difficult time later on.

Also you have a extremely unoptimized brute force. If you are dividing by a number to see if it a prime factor then the largest possible would be the sqrt since sqrt * sqrt = number. So no need to check beyond that.

Generally you want to make a sieve up to the sqrt then find one that it is divisible by.

Something like this(don't have much time so it isn't optimized):

std::vector<bool> primes(sqrt + 1, true); //starts at 0 so add 1
for(int i = 2; i < fourthRoot; ++i) //you can remove the evens with the inital sieve I normally do then increment by 2 starting at 3
{
    if(primes.at(i)) //it is prime so remove all multiplications
    {
        for(int j = i*i; j <= sqrt; j += i)
        {
            primes.at(j) = false;
        }
    }
}

//if it is even (and greater than 1) it is prime. 

Then you can check if it is a factor by doing something like:

std::vector<int> factors;

if(number % 2 == 0) //even
{
    factors.push_back(2);
}

for(int i = 3; i < sqrt; i += 2)
{
    if(primes.at(i) && numbers % i == 0) //it is prime and a factor
    {
        factors.push_back(i);
    }
}

*edit here is a link for a basic sieve
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

[ECEsasha]

Ah, I didn't know about the square root rule for prime factors.

Thanks! I'm trying again with Sieve.
I've used Sieve in my programming methodology class earlier on this semester and I'm not sure why I didn't think to use it...

Yeah, I need a lot more practice with optimizing my code, which is why I started Project Euler... this is fun :D