Ad
  • Default User Avatar

    Your "isPrime" function is flawed! You need to add 1 to the upper end of the range or else it returns true for all perfect squares.

  • Default User Avatar

    The given implementation can be improved by just changing the upperbound of the range to be int(math.sqrt(n))+2

    Still probably not the most efficient approach, but there's no point in checking numbers above the sqrt(n)+1.

    Edit:
    Actually I think it does not matter since the return statement will exit the function before those higher values are tested.

  • Custom User Avatar

    Your code is much more efiicient

  • Custom User Avatar

    What you said is correct, if the number has a large factor, it will be time consuming.Please refer to my solution.

  • Custom User Avatar

    I tried to check if n is a prime number when each time n changes. Hope this can help.

  • Custom User Avatar

    This implementation takes too long when n is big and can only be factorized like (2)(n') where n' is half of n(which is a big prime number).
    for example, it takes a long long time to find the primeFactors(76587634333).

    My implementation checkes if n is a prime number after each time n changes and it works well for all cases, although it seems long.

    Hope the idea of 'checking if n is a prime number' would help you improve your algorithm.