ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
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
Re: 'Time limit exceeded' in Python 3.6
Posted by Rumman Sadik 20 Aug 2018 22:28
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