fork download
copy 
  1. def get_primes(limit):
  2.     is_prime = [True]*(limit+1)
  3.     is_prime[1] = False
  4.     i = 2
  5.     while i <=limit :
  6.         if is_prime[i] == True:
  7.             j = 2*i
  8.             while j < limit:
  9.                 is_prime[j] = False
  10.                 j+=i
  11.         i+=1
  12.     p = []
  13.     for i in range(2,limit+1):
  14.         if is_prime[i] == True:
  15.             p.append(i)
  16.     return p
  17. T = int(input())
  18. for _ in range(T):
  19.     low,high = list(map(int,input().split()))
  20.     limit = int(high**0.5)+1
  21.     p = get_primes(limit)
  22.     is_prime = [True]*(high-low+1)
  23.     for p1 in p:
  24.         start = int(low/p1)*p1
  25.         if start < low:
  26.             start += p1
  27.         if start == p1:
  28.             start += p1
  29.         current = start
  30.         while current <= high:
  31.             is_prime[current-low] = False
  32.             current += p1
  33.     for i in range(low,high+1):
  34.         if is_prime[i-low] == True:
  35.             print(i)
  36.     print()
  37.  
Runtime error #stdin #stdout #stderr 0.01s 27664KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Traceback (most recent call last):
  File "./prog.py", line 17, in <module>
EOFError: EOF when reading a line
https://ideone.com/2PEmjl
problem PRIME1, based on SPOJ submission 23985548 (PYTHON3), 2019-06-27 20:27:41
language:
Python 3 (python  3.9.5)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!