import math

def is_prime(n):
    if n == 1:
        return False
    else:
        for i in range(2, n):
            if n%i==0:
                return False
        return True

def improved_is_prime(n):
    if n == 1:
        return False
    elif n == 2:
        return True
    elif n%2 == 0:
        return False
    else:
        sqr = int(math.sqrt(n))
        for x in range(3, sqr+1, 2):
            if n%x == 0:
                return False
        return True
    
def iterations_is_prime(n):
    if n == 1:
        return False, 0
    else:
        for i in range(2, n):
            if n%i==0:
                return False, i-1
        return True, n-2


def improved_iterations_is_prime(n):
    if n == 1:
        return False, 0
    elif n == 2:
        return True, 0
    elif n%2 == 0:
        return False, 1
    else:
        sqr = int(math.sqrt(n))
        found = False
        x = 3
        ni = 0
        while x <= sqr:
            ni = ni + 1
            found = n%x == 0
            if found:
                break
            x = x + 2
        return not found, ni

def prime (maxn):
    lp = []
    for i in range(2, maxn+1):
        if improved_is_prime(i):
            lp.append(i)
    return lp