1 / 5
Jul 2015

How to generates primes with PYTH 2.7 in 0.00 sec?

There are 144 people that done with PYTH 2.7 in 0.00 sec
http://www.spoj.com/ranks/PRIME1/lang=PYTH%202.7,start=14043

I used many tricks to reduce my execution time, likes:
replacing IO with sys.stdin and sys.stdout (reduce times of clearing IO buffer),
sieve of Eratosthenes,
replacing loops of accessing list with map(), filter(), [... for ... in ... ], list slices, if it's possible to work,
...

At last, my best time is 0.03 sec. I don't know that how to improve my execution time to 0.00 sec with PYTH 2.7.

By the way, with other compilers of Python, numerix and Francky have the best time, but it's not with PYTH 2.7.
Is something special with PYTH 2.7?

  • created

    Jul '15
  • last reply

    Aug '15
  • 4

    replies

  • 1.2k

    views

  • 3

    users

  • 2

    likes

  • 3

    links

Use segmented sieve for faster results.

PY2.7 have a faster startup, so it is possible to reach 0.00s more easily.

Nice, in that case it is only optimisation in the code. You already did a very good job.
There are some ways to deal with array that are faster than others ; eg to set a whole range to 0 (or 1) without a for loop.

Hint : for any problem, if you want to optiz ; find the bottleneck (where do you compute the most often), and experiment other methods.

21 days later

I believe it has something to do with test cases. (@francky, can you verify this?)
I had a 0.00s submission10 long ago. (that used trial division and segmented sieves, completely unoptimized.. takes maybe 0.2s now)

Also, @francky's top PyPy solution is a Python 2.7 solution. I think it (0.02s) is safe to assume that is best possible time in Python 2.7.