Calculating prime factor of a huge number.

This is a discussion on Calculating prime factor of a huge number. within the C Programming forums, part of the General Programming Boards category; For Euler challenges requiring large numbers I'd really recommend a language that supports them natively, e.g Python (learning the basics, ...

  1. #16
    The larch
    Join Date
    May 2006
    Posts
    3,573
    For Euler challenges requiring large numbers I'd really recommend a language that supports them natively, e.g Python (learning the basics, essentially programming in C-style, should not be too hard).

    It also sort of seems to me that the algorithm might be not quite as efficient as possible (checking is_prime means trying to divide with the same values over and over).

    Think about it.

    For example, the prime factors of 38962 are 2, 7, 11, 11 and 23. The largest prime factor is 23. Do you really need to check all (odd) numbers all the way up to sqrt(38962) = 197 ? (It should be possible to find the prime factors using modulus around 13 times, not 98 * some_n times.)
    Last edited by anon; 02-20-2009 at 11:12 AM.
    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).

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Number Guessing
    By blacknapalm in forum C Programming
    Replies: 2
    Last Post: 10-01-2008, 01:48 AM
  2. Problem running prime number test.
    By galactic_ronin in forum C++ Programming
    Replies: 25
    Last Post: 02-20-2008, 11:21 AM
  3. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 05:20 AM
  4. Array of boolean
    By DMaxJ in forum C++ Programming
    Replies: 11
    Last Post: 10-25-2001, 11:45 PM
  5. How is to check prime number?
    By Unregistered in forum C Programming
    Replies: 7
    Last Post: 10-04-2001, 11:36 PM

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