Witam !
Problem jak w temacie, program działa za długo :(
Link do zadania: https://www.spoj.com/problems/PRIME1/
Code:
from math import sqrt
def candidate_range(n):
cur = 5
incr = 2
while cur < n+1:
yield cur
cur += incr
incr ^= 6 # or incr = 6-incr, or however
def sieve(end):
prime_list = [2, 3]
sieve_list = [True] * (end+1)
for each_number in candidate_range(end):
if sieve_list[each_number]:
prime_list.append(each_number)
for multiple in range(each_number*each_number, end+1, each_number):
sieve_list[multiple] = False
return prime_list
t = int(input())
list_of_primes = sieve(int(sqrt(1000000000)))
def is_prime(number):
if (number<2):
return 0
for k in list_of_primes:
if (number%k == 0 and k!=number and k<=int(sqrt(number))):
return 0
break
return 1
while t:
x,y = map(int, input().split())
for number in range(x,y+1):
if(is_prime(number)==1):
print(number)
print()
t+=-1