It is required to find the smallest divisor of the number n> 1. The time limit is 1000 ms. Apparently checked for very large numbers. I was able to reach the 55th test and get to the time limit.

How to improve optimization?

Code:

from math import sqrt def mindivisor(n): if n % 2 == 0: return 2 if n % 3 == 0: return 3 if n % 5 == 0: return 5 i = 7 while n % i != 0: i += 2 if i % 10 == 5: i += 2 if i > sqrt(n): return n else: return i n = int(input()) print(mindivisor(n))
  • indent for if i > sqrt(n) check - jfs
  • @jfs thanks! Here the dog was buried - slemik

3 answers 3

 while n % i != 0:

Here you check all the numbers up to n , although you can only up to sqrt(n) . It seems to me that the main problem is this. Try without any checks, just in the forehead:

 def div(n): for i in range(2, int(sqrt(n)+1)): if n%i == 0: return i return n
  • I started with this, then I shortened it. Minimum removing even - bust in 2 times reduced. Also, the search goes to the root of n, just a check inside - slemik
  • Yes, this method is the fastest. There is nothing to accelerate here :) - Denis
  • @Denis: there are faster methods for factoring large numbers, for example, the quadratic sieve method - jfs
  • for large numbers the border is wrong. To understand why (one of the possible reasons) see: Lyap in Python: x + 1.0 <x . It is better to use ceil(sqrt(n))+1 to deal with integers. Although here it is rather a theoretical problem: a similar algorithm with 100-bit numbers will not reach the right border. - jfs

Summary Code:

 from math import sqrt, ceil def mindivisor(n): if n % 2 == 0: return 2 if n % 3 == 0: return 3 if n % 5 == 0: return 5 i = 7 while n % i != 0: i += 2 if i % 10 == 5: i += 2 if i > ceil(sqrt(n)) + 1: return n return i n = int(input()) print(mindivisor(n))

The problem was indentation before if i> ceil (sqrt (n)) + 1:

    A variant of the algorithm for iterating over dividers with c wheel factorization for factors 2 and 3 . Dividers are generated in steps of 2 and 4 in turn. Translated from D code :

     from math import ceil, sqrt def mindivisor(number): # manually test 1, 2, 3 and multiples of 2 and 3 if number == 1: return 1 elif number % 2 == 0: return 2 elif number % 3 == 0: return 3 # we can now avoid to consider multiples # of 2 and 3. This can be done really simply # by starting at 5 and incrementing by 2 and 4 # alternatively, that is: # 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, ... # we don't need to go higher than the square root of the number divisor = 5 increment = 2 sqrt_n = ceil(sqrt(number)) while divisor <= sqrt_n: if number % divisor == 0: return divisor divisor += increment increment = 6 - increment # 2 -> 4 -> 2 return number # number is prime 

     <script type="text/javascript" src="https://cdn.rawgit.com/brython-dev/brython/3.4.0/www/src/brython.js"></script><body onload="brython()"><script type="text/python"> from math import ceil, sqrt def mindivisor(number): # manually test 1, 2, 3 and multiples of 2 and 3 if number == 1: return 1 elif number % 2 == 0: return 2 elif number % 3 == 0: return 3 # we can now avoid to consider multiples # of 2 and 3. This can be done really simply # by starting at 5 and incrementing by 2 and 4 # alternatively, that is: # 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, ... # we don't need to go higher than the square root of the number divisor = 5 increment = 2 sqrt_n = ceil(sqrt(number)) while divisor <= sqrt_n: if number % divisor == 0: return divisor divisor += increment increment = 6 - increment # 2 -> 4 -> 2 return number # number is prime def show(n): print(f"{n} -> {mindivisor(n)}") show(2209) show(2201) # try your own input from browser import document, alert @document["mybutton"].bind("click") def on_click(event): show(int(document["zone"].value)) </script> <input id="zone" value="2021"><button id="mybutton">mindivisor</button></body>