Home python Minimum Prime Divisor Problem

# Minimum Prime Divisor Problem

Author

Date

Category

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

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

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

Output data: Print the answer to the problem.

I 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 over 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
print(i)
``````

I can’t figure out what the mistake is?

I would do 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())
print(prime_f(N))
``````

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

Not quite sure why “i * i & lt; = N”?
If, after while, immediately write the remainder inequality to zero, then all the rules work)

``````N = int(input())
i = 2
while N%i != 0:
i += 1
print(i)
``````

``````N = int(input())
s=1/2
a=N
b=int(N**s)
for i in range(2,b+1) :
if N%i == 0:
if a > i :
a=i
print(a)
``````

The program has passed the time test on Sirius.

``````Python:
a = int(input())
b = a - 1
while a < 2:
print('Number need to be more than "2"')
a = int(input())
while a % b != 0:
b = b - 1
if a % b == 0:
b = a // b
print(b)
``````

while N% i! = 0 is a test for the prime number, all even numbers except 2 will be composite, which means they must be further divided until you hit a prime number that divides the input without a remainder.

Why spend time searching for the correct question and then entering your answer when you can find it in a second? That's what CompuTicket is all about! Here you'll find thousands of questions and answers from hundreds of computer languages.