Thread: prime factorisation program

  1. #1
    Registered User
    Join Date
    Jul 2008
    Posts
    9

    prime factorisation program

    there is a question about making a program to find prime factorization.

    And it says : " Your algorithm must be quicker for some types of numbers than for others of similar size"

    i dont know what "others of similar size" means.

    i guess that kind of numbers : 2^n.

    since i set my initial test number t=2

    but i cant find those numbers of "similar size"

  2. #2
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    Quote Originally Posted by szpengchao View Post
    And it says : " Your algorithm must be quicker for some types of numbers than for others of similar size"
    The algorithm's quicker for numbers that have 2 as the only prime factor; "similar size" may refer to their length ie the no. of digits in 'em.

  3. #3
    Math wizard
    Join Date
    Dec 2006
    Location
    USA
    Posts
    582
    Do you mean having 60 as the input and "2, 2, 3, 5" as the output, reducing a number to prime factors? This shouldn't be too difficult. Start with 2, the lowest possible prime number. If "Input % 2 == 0", then factor 2 out of it. Write the output and divide by 2. If the number still is a multiple of 2, repeat until it is not. If "Input % 2 != 0", then go to the next prime number, 3. Continue in this fashion until you've reached or exceeded the square root of your remainder. Take 127. You can't take any primes out of it, even with something as high as 11, but 13, the next one, is above the square root of this value so you don't need to do 13 and above. This is the way I do it in my head and on paper.
    High elevation is the best elevation. The higher, the better the view!
    My computer: XP Pro SP3, 3.4 GHz i7-2600K CPU (OC'd to 4 GHz), 4 GB DDR3 RAM, X-Fi Platinum sound, GeForce 460, 1920x1440 resolution, 1250 GB HDD space, Visual C++ 2008 Express

  4. #4
    Registered User
    Join Date
    Jul 2008
    Posts
    9
    Quote Originally Posted by itCbitC View Post
    The algorithm's quicker for numbers that have 2 as the only prime factor; "similar size" may refer to their length ie the no. of digits in 'em.


    so i guess u mean, the algorithm is quicker for 2^n than other numbers with the same number of digits???

  5. #5
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    Quote Originally Posted by szpengchao View Post
    so i guess u mean, the algorithm is quicker for 2^n than other numbers with the same number of digits???
    yep!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. prime number program code
    By jd7joe in forum C++ Programming
    Replies: 1
    Last Post: 11-17-2005, 10:14 AM
  2. Date program starts DOS's date
    By jrahhali in forum C++ Programming
    Replies: 1
    Last Post: 11-24-2003, 05:23 PM
  3. C Program for Prime Numbers
    By mmuhlenb in forum C Programming
    Replies: 12
    Last Post: 02-19-2003, 04:55 AM
  4. problem with my prime number program
    By datainjector in forum C Programming
    Replies: 4
    Last Post: 07-12-2002, 12:30 PM
  5. My program, anyhelp
    By @licomb in forum C Programming
    Replies: 14
    Last Post: 08-14-2001, 10:04 PM