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

Re: 'Time limit exceeded' in Python 3.6

def prime(n):

for i in range(2, n):

if n % i == 0:

return False

return True

k = int(input())

for i in range(k):

n = int(input())

count = 0

for f in range(2, 100):

if prime(f) == True:

count += 1

if count == n:

break

print(f)

I have same problem