ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1086. Cryptography

'Time limit exceeded' in Python 3.6
Posted by az 10 Mar 2018 05:32
It looks like a very simple problem. In pure C, but not in Python! :)
'Time limit exceeded' despite using precomputed tuple of primes (first 100 and each 100th or 50th), Eratosthenes' sieve, optimizations, wheel factorization etc.
Time is 2.10-2.30 regardless of method !!! WTF???
On my PC it finds a prime very fast:

Enter the number... 14999
14999-th prime number is 163819
Elapsed time is 0.0010540485382080078

On my computer and python implementation (Intel i3, Linux Fedora 27/ CPython 3.6.4) average time per prime is about 1 ms o less.

How to solve the problem in this strangely slow Python implementation?

Edited by author 10.03.2018 05:38