"""
Sieve Technique
To check prime numbers from 1 to N.
Part of competitive programming number theory.
logic - go from 1 to N and call check_prime() maintain a boolean table for each number .
        mark the multiples of current n False since prime numbers has only 1 and n as it's multiple.
        which reduces the time complexity.
"""

import math


# def primeSieve(n):
#     isprime = [True for i in range(n + 1)]
#     isprime[0] = isprime[1]= False
#     # isprime[1] = False
#     i = 2
#     while i * i <= n:
#         if isprime[i] == True:
#             j = i * i
#             while j <= n:
#                 isprime[j] = False
#                 j += i
#             i += 1
#     print(isprime)


def primeSieve(n):
    isprime = [i for i in range(2, n + 1)]
    for i in range(2, int(math.sqrt(n))):
        if i in isprime:
            for j in range(i * i, n + 1, i):  # previously it was 2 * i it should be i*i
                if j in isprime:
                    isprime.remove(j)
    print(isprime)


primeSieve(100)
