Sign in
Microsoft.com
 
Microsoft
 
 
 

locked
Shortest Algo RRS feed

 > 

  • Question

  • Question
    Sign in to vote
    0
    Sign in to vote

    wat is the shortest algo for obtaining prime factorisation of any number..

    i dont want to loop from 1 to that number..

    Friday, September 14, 2007 5:11 AM

All replies

  • Question
    Sign in to vote
    0
    Sign in to vote
    A loop going from 1 to n/2 should suffice your requirement as there cannot be any number which is greater than half of the number and still be a factor of that number.

    For example = let us take the number 60 you cannot have any number greater than 30 which is a factor of 60.

    So The time complexity has to O(n/2).
    Friday, September 14, 2007 8:23 PM