Prime number

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

Recommended Posts

Prime number
Prime number 2 in Python
Infinite prime number generator in Python3
Prime number generation program by Python
It's a prime number ... Counting prime numbers ...
Prime number enumeration in one line
Base number
Project Euler # 7 "1000 1st prime number" in Python
Natural number generator
[For competition professionals] Prime number, divisor, prime factorization summary
Prime number enumeration and primality test in Python
Arbitrary bit number prime creation Python code RSA
Judge whether it is a prime number [Python]
Positive number encryption
I made a prime number generation program in Python
I made a prime number generation program in Python 2