Shortest Algo RRS feed

  • Question

  • 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

  • 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