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

Recommended Posts

nombre premier
Premier nombre 2 en Python
Générateur principal infini en Python3
Générateur de nombres premiers par Python
C'est un nombre premier ... Comptez les nombres premiers ...
Énumération des nombres premiers sur une ligne
Numéro de base
Projet Euler # 7 "1000 1er nombre premier" en Python
Générateur de nombres naturels
[Pour les professionnels de la concurrence] Résumé des facteurs premiers, des réductions et des facteurs premiers
Énumération des nombres premiers et jugement des nombres premiers en Python
Création arbitraire de nombres premiers de bits Code Python RSA
Juger s'il s'agit d'un nombre premier [Python]
Chiffrement des nombres positifs