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.
|
|
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
|
|
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 |
RSS