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
ericwen46: 2022-04-26 06:54:58

Get an AC with Java, 1.81s for two inputs :)

weathervane: 2021-07-19 09:19:45

Without knowing the maximum number of test cases it is impossible to know if a submission has any chance of being within the time limit.

<== 2 test cases. Each test case ~ 2000000 lines.

Last edit: 2021-08-04 10:32:20
nadstratosfer: 2020-07-22 23:35:36

panny, input is large so sieve works, but your current method can do better here as well.

panny: 2020-07-22 12:07:59

first i precompute the primes using sieve upto sqrt(n) then check it divides or not the given number.But it takes 5.15sec ,is there any other approach or algo??

rofiqul: 2019-08-03 21:18:49

i think my answer is correct,but i get runtime error frequently
<= Reply Check outer for loop bounds in your last submission.

Last edit: 2019-08-14 18:23:43
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.


Added by:julkas
Date:2018-06-10
Time limit:60s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All