MMFLPDIV  Least prime divisor
Given odd integer n > 2 compute its least prime divisor.
Input
Each line of input contains one random odd integer number 2 < n < 10^{8} (100 000 000). Input terminates with 0 (zero). There will be two input files.
Output
For each n print its least prime divisor on new line.
Example
Input: 3 9 11 15 49 0
Output: 3 3 11 3 7
hide comments
wisfaq:
20180614 21:31:34
Last edit: 20180614 21:34:47 

julkas:
20180614 09:29:57
@nadstratosfer Your solution is fast. My overall C++ time ~ 1.85s 2x0.6s for sieve and ~ 0.65s for rest (scanf/printf...). PyPy sieve ~ 4.4s. Exactly same Python2 code is very slow ~ 47s. I will try some premature opt for Python/PyPy. Anyway may be for given input brute force approach would be better choice. 

nadstratosfer:
20180613 19:48:21
C bruteforce 1.02s, C primitive sieve 1.75s, Py2 bruteforce 22.80s, Py2 primitive sieve 7.47s. This is becoming a really nice problem when trying to get below these times. Got the idea how the optimal algo should work, but haven't figured out how to implement it correctly yet. In Python it might actually not yield much improvement because I'd have to replace the Cspeed idioms doing most of the work. Did you get your fast sieve working in Python also? 

julkas:
20180612 11:34:56
@nadstratosfer C++ sieve ~ 0.6s. Last edit: 20180613 12:21:20 

julkas:
20180612 09:07:21
@nadstratosfer It's interesting. Input generated with PyPy randint(). I use sieve in my PyPy solution  O(1) for query. So I will try brute force approach and C/C++. Thank's for comment. My best wishes. 

nadstratosfer:
20180612 06:09:14
Bruteforce outperforms sieve in C by a large margin. Perhaps updating testcases so that they're heavy in large primes could change this? 
Added by:  julkas 
Date:  20180610 
Time limit:  60s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 