TLE in prime game

1

I’ve used sieve to calculate no of prime
But i got TlE
Please help
Thanks in advance
Link to my solution:
https://www.codechef.com/viewsolution/42513446

2

Please recheck standard sieve of eratosthenes algorithm and improve your conditions.
eg: in your code j is compared with 1e6, but it should be j*j <= 1e6 if i am not wrong.
PS:- I might be wrong, but I feel improving to standard sieve might help.

3

Use faster I/O.

4

Here’s AC Code. You need to optimise your code.

  1. Sieve might want to run in O(N Log(Log(N)) time.
  2. Use faster IO.
from numpy import cumsum
from math import sqrt
from sys import stdin, stdout

def sieve():
    size = 10**6 + 1
    prime = [0]*size
    for i in range(3, size, 2):
        prime[i] = 1
    prime[2] = 1
    for i in range(3, int(sqrt(size))+1, 2):
        if prime[i] == 1:
            for j in range(i*i, size, i):
                prime[j] = 0
    return cumsum(prime)

def main():
    count = sieve()
    for test in range(int(input())):
        a, b = map(int, stdin.readline().strip().split())
        print("Chef" if count[a]<=b else "Divyam")

main()