1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Project Euler problem 3

  1. Aug 27, 2009 #1
    What is the largest prime factor of the number 600851475143 ?

    My attempt:
    Code (Text):

    #include <stdafx.h>

    int main()
    {
        int num1, num2, num3, num4, lrgprime, sum;
        lrgprime=num2=num4=sum=0;
        for (num1=2; num1<300425737572; num1++) {
            num2=600851475143%num1;

            if (num2==0) {
                for (num3=2; num3<=num1; num3++) {
                    num4=num1%num3;
                    if (num4==0 && num1==num3 && num1>=lrgprime)
                        lrgprime=num1;
                }      
            }  
        }
        printf("This is the largest prime factor: %d", lrgprime);
        return 0;
    }
    The machine is just not running this code

    What did I do wrong?
     
  2. jcsd
  3. Aug 27, 2009 #2
    check with some smaller numbers first. see whether you get anything
     
  4. Aug 27, 2009 #3
    Two problems. First, 600851475143 is too large to store in an int (which is usually 32 bits and only goes up to about 2 billion). Try using long longs instead of ints. Second,
    Code (Text):

            if (num2==0) {
                for (num3=2; num3<=num1; num3++) {
                    num4=num1%num3;
                    if (num4==0 && num1==num3 && num1>=lrgprime)
                        lrgprime=num1;
                }      
            }
     
    doesn't do what you want. It eventually always sets lrgprime to num1, even when num1 has divisors. You need to use a break statement to break out of the loop if num4 == 0 and num1 != num3.
     
  5. Aug 27, 2009 #4
    1) stdafx.h is not a standard header
    2) The maximum value of a 32-bit signed int is 2147483647. Of course, there is no reason to use integers for this task. The largest basic type you could use would be "unsigned long long", which has a maximum value of 18446744073709551615
    3) Your code is a mess...you have tons of useless auxiliary variables and have split things into multiple lines just making it more confusing than it should be.
    4) This is not an efficient approach, and will take too long on a big number.

    Code (Text):
    #include <iostream>
    #include <limits>

    typedef unsigned long long BigInt;
    using namespace std;

    BigInt largest_prime_factor( const BigInt &x )
    {
        //find factors
        for(BigInt y = x/2; y>2; --y)
        {
            //check factors
            if( x%y == 0 )
            {
                //check if factor is prime
                for(BigInt z=2; z<y; ++z)
                    if( y%z == 0 )
                        goto not_prime;
                return y;
            }
    not_prime: ;
        }
        return x;
    }

    int main()
    {

        cout << "Max value = " << numeric_limits<BigInt>::max() << "\n";
        cout << largest_prime_factor( 600851475143 );
    }
     
    Last edited: Aug 27, 2009
  6. Aug 28, 2009 #5
    Code (Text):
    for(BigInt y = x/2; y>2; --y)
    Just a suggestion: since the largest prime factor of x cannot not exceed x0=(int)sqrt(x), it pays to start at x0, especially for large numbers.
     
  7. Aug 28, 2009 #6
    Thank you so much, I am gonna save this page up, go home and try it. I have been struggling on this problem for 3 days.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Project Euler problem 3
  1. 3 to 5 decoder problem (Replies: 1)

Loading...