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 < 108 (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: 2018-06-14 21:31:34

Last edit: 2018-06-14 21:34:47
julkas: 2018-06-14 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: 2018-06-13 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 C-speed idioms doing most of the work. Did you get your fast sieve working in Python also?

julkas: 2018-06-12 11:34:56

@nadstratosfer C++ sieve ~ 0.6s.

Last edit: 2018-06-13 12:21:20
julkas: 2018-06-12 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: 2018-06-12 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:2018-06-10
Time limit:60s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All