[PYTHON] nombre premier

import math


"""
Given list of integer and find primes
"""
l = list(range(1, 101))
def is_prime(x):
    if x == 1:
        return False
    upper_limit = int(math.sqrt(x)) + 1
    for i in range(2, upper_limit):
        if x % i == 0:
            return False
    return True

primes = []
for i in l:
    if is_prime(i):
        primes.append(i)
print(primes)


"""
Given integer and find primes which are less than the integer
"""
n = 101

if n > 2:
    # it is not necessary to check all number which is less than the integer
    # create list of odd integer
    l = list(range(3, n, 2))
    # 2 is the minimum prime
    primes = [2]

    for i in l:
        f = False
        for j in primes:
            # Compare upto sqrt(i) then if there have not been any numbeer
            # which can divide i, i is prime
            if j * j > i:
                f = True
                break
            if i % j == 0:
                break
        if f:
            primes.append(i)
    print(primes)

ref: http://www.geocities.jp/m_hiroi/light/python01.html#chap22