+ 4

How to recognize if a number is prime factor?

I have alreasy found some thing but it's not efficient! https://code.sololearn.com/cBLxqISeh8p8/?ref=app

14th Feb 2019, 8:26 AM
Amin
5 ответов
+ 5
Here is something you can do to make it efficient. Replace the upper bound to ceil(sqrt(p)) so you can avoid checking some numbers. (obviously you need to do: from math import *)
14th Feb 2019, 8:34 AM
[Abandoned]
[Abandoned] - avatar
+ 4
1. Do you need to count the number of factors? Returning False when encountering any factor is enough. 2. Instead of going up to p, stop if it goes past the square root. If there is a factor strictly higher than it, there is also a factor strictly lower than it with the product of the two giving you p. But you have already tested numbers lower than the square root by this point. And if you don't have access to the square root function, use p/2 as the limit instead.
14th Feb 2019, 8:41 AM
Zen
Zen - avatar
+ 4
Like above mentioned, you should test within the range of 2 and ceil(sqrt(n)). This is because everything after sqrt(n) is a factor if something below it is a factor.
14th Feb 2019, 11:31 PM
👑 Prometheus 🇸🇬
👑 Prometheus 🇸🇬 - avatar
+ 3
Here is something you can do to make it efficient. Replace the upper bound to ceil(sqrt(p)) so you can avoid checking some numbers. (obviously you need to do: from math import *)
14th Feb 2019, 8:34 AM
[Abandoned]
[Abandoned] - avatar
+ 1
Here: https://code.sololearn.com/cMtYs52rMIq3/?ref=app You can make it better using a better import. Edit: added a correction thanks to Bennett Post (the upper limit in range isn't inclusive)
17th Feb 2019, 11:32 AM
Federico Corradini
Federico Corradini - avatar