PRIME1 TLE with python 3

[jacob_01]

HI !
I got tle with this 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+1)))

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

I used python 3.5
Can anyone tell me a hint how to fix it

[simes]

Sure! You need to make it faster.

list_of_primes = sieve(int(sqrt(1000000000+1)))

How long does this bit take to run?

[jacob_01]

I change this line
list_of_primes = sieve(int(sqrt(100001)))
But now I had WA

[simes]

list_of_primes = sieve(int(sqrt(1000000000+1)))
I think this is correct, I just wondered how long it took.

In the is_prime function, you can terminate the loop early sometimes, you don’t need to go right through the list of primes. I don’t know whether that’ll be enough to get AC though.

[jacob_01]

Okay, but I terminate this loop to square of the checking number. I get only numbers form list_of_primes to sqrt form checking number

[simes]

Here’s a test

def is_prime(number):
    if (number<2):
        return 0
    x = 0
    for k in list_of_primes:
        x += 1
        if (number%k == 0 and k!=number and k<=int(sqrt(number))):
            print(x)
            return 0
            break
    print(x)
    return 1

is_prime(7)

There are 3401 primes in the list, how many times will the loop execute when testing whether 7 is prime? i.e. what number will be printed?