python – Minimum Prime Divisor Problem


Just started learning Python on the Sirius platform. I was able to solve all the other problems from the "while" topic, except for one problem, which does not allow me to go on the following topics. The task "The minimum prime divisor of a number".

Condition: An integer is given, at least 2. Print its smallest prime divisor. You cannot use additional libraries (math, etc.)!

Input data: Enter a positive integer N <= 2 * 10 to the 9th power.

Output data: Print the answer to the problem.

Tried to solve it by writing code with while, but my answer does not count because the program is running too long. It is recommended to organize a loop that iterates through the divisors up to the root of the number N: while i*i <= N: but I cannot figure out how to do this.

My Python code (gives the error "The program took too long and was interrupted" or "The program throws an error during execution"):

N = int(input())
i = 2

while i*i <= N:
    if N%i != 0:
        i += 1

Can't figure out what the mistake is?


I would do like this:

def prime_f(n):
    if n%2 == 0: return 2
    i = 3
    while n%i != 0 and i*i <= n:
        i+= 2
    if i*i <= n: return i
    return n

N = int(input())


We check 2 separately, then only odd ones, and up to the root of N – otherwise N is simple in itself.

Scroll to Top