Euler's problem #3

This is a discussion on Euler's problem #3 within the C++ Programming forums, part of the General Programming Boards category; http://projecteuler.net/index.php?section=problems&id=3 "The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the ...

  1. #1
    Registered User
    Join Date
    Oct 2007
    Posts
    66

    Euler's problem #3

    http://projecteuler.net/index.php?section=problems&id=3

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

    What is the largest prime factor of the number 600851475143 ?"

    --

    Code:
    unsigned long long int y = 600851475143;	// wow thats long
    
    for ( int i = 0; i<(y/2); ++i)
    {
    	std::cout << "Check " << i << "\n";
    }
    Just one quick question, I'm already sure this is the wrong approach so I'm researching the right way to do it in C++, but, this has me wondering. Is this a safe-check? That is, will y/2 end up being the exact value (a decimal, compared to an int which I assume it would just drop the 1.5 value to 1?) I would try running it but well it has to loop through 30 million times and my computer isn't that fast
    "When your work speaks for itself - don't interrupt!"

    -Samantha Ingraham.

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    It you check it against all values in that range, you'll find what it is and isn't divisible by, but how does that help you to find the prime factors?

    For example, 13195 is also divisible by 35 (5 * 7) but that is not a prime factor. You might need to look for a different approach.

    Since this is a challenge you might rather figure it out yourself or seek materials on prime factorization on the internet yourself.

    When concerning prime factorization, you might be more interested in the square root of the value, rather than half of it.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    Registered User
    Join Date
    Oct 2007
    Posts
    66
    Yeah I clearly have the wrong approach going on lol. I didn't have any clue at all on where to start until I did some research, so now I'm working on solving the problem.

    But I'm still curious, will i<(y/2) work and give me the number 300xxxxxxxxx.5 which would (I assume) round down instead of up? (Because I assume it would just drop that value, but I dunno...) Also, another thing I just realized an int probably couldn't store that number divided by two so it would probably eventually fail. (I dunno why I thought it would only run 30 million times lol, must have miscounted...though I knew it wasn't in the millions. Maybe I'm just crazy)
    "When your work speaks for itself - don't interrupt!"

    -Samantha Ingraham.

  4. #4
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Yes, integer division truncates (chops off decimal part).

    Also, another thing I just realized an int probably couldn't store that number divided by two so it would probably eventually fail.
    That too.

    In any case, I did this with Python (where large integers are no problem) and it takes about a blink of an eye to get the answer (with a suitable algorithm - perhaps with a few thousand divisions, rather than millions).
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Memory problem with Borland C 3.1
    By AZ1699 in forum C Programming
    Replies: 16
    Last Post: 11-16-2007, 11:22 AM
  2. Someone having same problem with Code Block?
    By ofayto in forum C++ Programming
    Replies: 1
    Last Post: 07-12-2007, 09:38 AM
  3. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 03:51 PM
  4. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 07:54 PM
  5. beginner problem
    By The_Nymph in forum C Programming
    Replies: 4
    Last Post: 03-05-2002, 05:46 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21