1

Can't find the prime factor of 600851475143 for projecteuler. My code successfully computes the largest prime factor of the test number 13195 and every test number I throw at it, but somehow it degrades with the large prime number. Do you know why?

#include <iostream>     
#include <queue>  
using namespace std;
int split(int split);
int largestprimefactor(priority_queue<int> myints);
int main()
{
int response = 2;
do{
    priority_queue<int> myints;
    int number;
    cout << "Please enter a number: ";
    cin >> number;
    myints.push(number);
    int lcf = largestprimefactor(myints);
    cout << endl << "Largest prime factor is: " << lcf;
    cout << endl << "Again?(1 for yes 2 for no): ";
    cin >> response;
}while(response == 1);
}
uint64_t split(uint64_t split)
{
if(split%2 != 0)
{
    if((split/2))%2 == 0)
        for(uint64_t i = (split/2)-1; i>1; i=i-2)
            if(split%i == 0)
                return i;
    else
        for(uint64_t i = (split/2); i>1; i=i-2)
            if(split%i == 0)
                return i;
    return 1;
}
else
    return 2;
}
int largestprimefactor(priority_queue<int> myints)
{
// largestfactor holds the next number to be tested for primeness in the queue
do{
    int largestfactor = myints.top();
    myints.pop();
    //splat will hold the first factor split finds of the top item in the queue
    int splat = split(largestfactor);
    //if it holds a 1 then that means that there are no factors
    if(splat != 1 && largestfactor)
    {
        myints.push(splat);
        myints.push(largestfactor / splat);
    }
    else
        return largestfactor;   
}while(myints.top() > 1);
}
Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343
CodeManiak
  • 1,903
  • 4
  • 19
  • 32

3 Answers3

2

Have you considered that 600851475143 is too large to store in a 32 bit int?

Look into what your compiler provides for 64 bit integer types.

timday
  • 24,582
  • 12
  • 83
  • 135
  • I tried it with longs and I got the same answer, my code spits out 2147483647 which has a remainder when divided by 600851475143 :( – CodeManiak Dec 23 '13 at 09:25
  • 2
    @CodeManiak: What size are longs on your system? try long long, or uint64_t – PlasmaHH Dec 23 '13 at 09:26
  • My system is crunching the numbers still... I"ll let you know! I can hear the processor humming... or the hard drive. Which one hums? The fan probably. Maybe I should get up and make a sandwich... Geez I know what prime I'm using next time I use RSA! – CodeManiak Dec 23 '13 at 09:29
  • 1
    There's no reason for a good solution to problem 3 not to run in under a second, even in a scripting language. Maybe you should reconsider your approach (as per comments on other answer). – timday Dec 23 '13 at 09:54
  • @CodeManiak have you change to long for "every" location, not just the beginning of the code? – Pham Trung Dec 23 '13 at 10:17
  • yeah it was because I changed everything to uint64 out of desperation. When I changed only the necessary int it ran much faster :) – CodeManiak Dec 23 '13 at 18:34
1

I might not be able to help you optimize your code (I'm not sure what you do in split), but here's an idea.

By the fundamental theorem of arithmetic, each number has a unique factorization into a product of primes. This means we can take a number and successively divide it by its prime factors until we reach 1. The last prime factor is the answer.

Now, you need only check prime factors up to sqrt(N). Note that this does not mean that the largest prime factor is less than sqrt(N), but that if there is a prime factor greater than sqrt(N), there is only one such prime factor.

This leads to the following O(sqrt(N)) algorithm:

long long largest_factor(long long number) {
    long long result = 0;
    for (long long i = 2; i * i <= number; ++i) {
        if (number % i == 0) {
            result = i;
            while (number % i == 0)
                number /= i;
        }
    }
    if (number != 1)
        return number;
    return result;
}

Running this on 600851475143 gives me the right answer.

sebii
  • 506
  • 2
  • 6
0

600851475143 >> 32 give 129, 600851475143 >> 64 give 3.10^-8. This number is too big to be represented as an int, but you can represent it with a 64 bit number as long long or a class designed to represent bigger integers.

UmNyobe
  • 22,539
  • 9
  • 61
  • 90
  • no, because long long is smaller than 2^64. – UmNyobe Dec 23 '13 at 09:36
  • 2^ 64 = 18446744073709551616 > 600851475143 – Толя Dec 23 '13 at 09:41
  • so I slightly optimized the "split" algorithm, but do you see any other ways to optimize this? It's still running on my laptop. Maybe one of you with a fast computer can try to run this and find the answer? :) – CodeManiak Dec 23 '13 at 09:42
  • 1
    @Толя ok you are correct. codemaniak the goal is for you to implement an efficient algorithm, that's the idead of project euler – UmNyobe Dec 23 '13 at 09:43
  • I agree, do you see any issues with my algorithm, or ways to improve? There might be an easier way to sieve through a numbers largest factors but my method was to just get rid of everything that is divisible by 2 and decrement by 2 starting at prime/2. Seems like thats the simplest and best method without implementing drastic measures. But whatever method I chose its drastically expensive because its been 20 minutes and I still don't have a number lol – CodeManiak Dec 23 '13 at 09:45
  • compute factors using prime decomposition. I gave an answer on a similar question. see http://stackoverflow.com/a/9945811/1122645. Btw this is a different question. – UmNyobe Dec 23 '13 at 09:47
  • So you implement the sieve of erasthenos to generate a prime table and then use that? interesting.... more work to do obviously. – CodeManiak Dec 23 '13 at 09:51
  • 1
    yes. if you know the prime factorization, you can compute the biggest divisor by removing the smallest term. 24 = (2^3) * 3, so you you know youu need to remove 2. btw make it nice, primes + factorization is recurring in project euler, you may want to reuse your code. – UmNyobe Dec 23 '13 at 09:56
  • If you think you can wander into Project Euler problems and tick 'em off with O(n) brute-force algorithms and a few simple optimisations that just give you a faster O(n), you will not get far at all, even if you ignore the minute runtime (for some problems a brute force approach would need 100s-1000s years runtime, and some even cosmic timescales). Learning to implement prime sieves is hardly "drastically measures"; it's an essential skill you absolutely must master if you're going to get anywhere with PE. – timday Dec 23 '13 at 11:39
  • 1
    @timday: true that you will need to implement a sieve for Euler, but a sieve isn't needed for this problem. What is needed, though, is *some* non-stupid factorization algorithm. Trial division up the the square root is easily good enough for this number, then there are a few simple improvements on that to bring the runtime from a fraction of a second down to a small fraction of a second :-) – Steve Jessop Dec 23 '13 at 11:43
  • @SteveJessop: ok, just looked back at my solutions to low-numbered PE problems from years ago. They're even simpler than I remember; yes, sieving doesn't come in until a bit later. – timday Dec 23 '13 at 11:55