'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*