素数

素数について。
　
素数生成のジェネレータ

def gen2(start=2, stop=1000000):
    pr = max(1, start - 1)
    while True:
        while pr < stop:
            pr += 1
            if all(pr%x != 0 for x in range(2, int(pr**0.5) + 1)):
                break
        yield pr

g = gen2()
for i in range(10):
    print(next(g), end=" ")
print()
# 2 3 5 7 11 13 17 19 23 29 

　
素因数分解

# 素因数分解
def factorial(n):
    if n in [0, 1]:
        return [n]
    result = []
    stop = int(n**0.5) + 1
    g = gen1()
    pr = next(g)
    while pr < stop:
        if n % pr == 0:
            result.append(pr)
            n //= pr
            continue
        pr = next(g)
    if n > 1:
        result.append(n)
    return result

g = gen2()
for i in range(10):
    print(next(g), end=" ")
print()

for i in range(0, 10):
    print(i, factorial(i))
# 0 [0]
# 1 [1]
# 2 [2]
# 3 [3]
# 4 [2, 2]
# 5 [5]
# 6 [2, 3]
# 7 [7]
# 8 [2, 2, 2]
# 9 [3, 3]
print(10**6, factorial(10**6))
# 1000000 [2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5]

import random
r = random.randint(1, 10**7)
# 5197227 [3, 7, 379, 653]