How to recognize if a number is prime factor?

Question

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

Answer 1

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 *)

Answer 2

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.

Answer 3

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.

Answer 4

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 *)

Answer 5

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)