def sieve(n):
    isPrime = [True] * (n + 1)
    isPrime[0] = isPrime[1] = False
    i = 2
    while i * i <= n:
        if isPrime[i]:
            j = i * i
            while j <= n:
                isPrime[j] = False
                j += i
        i += 1
    return isPrime