素数と合成数、素因数分解

素数と合成数、素因数分解

素数

 2 個の約数をもつ自然数のことを 素数 (prime number) といいます。1 の約数は 1 だけなので素数ではありません。2 は 1 と 2 を約数にもつので素数です。すなわち 2 は最小素数です。3 は 1 と 3 を約数にもつので、やはり素数です。

sympy.primerange()

 sympy.primerange(a, b) は a 以上 b 未満の素数を生成するジェネレータを返します。

# PC_01-1

import sympy

# 2~29の範囲内の素数を返すジェネレータ
p_g = sympy.primerange(2, 30)

print(p_g)
<generator object primerange at 0x059A4510>

 ジェネレータをリストに渡すと中身を列挙します。

# PC_01-2

# 2~29の範囲内の素数を列挙
p_list = list(p_g)

print(p_list)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

sympy.prime()

 sympy.prime(n) は (最小素数 2 から数えて) n 番目の素数を返します。

# PC_01-3

# 5番目の素数
p = sympy.prime(5)

print(p)
11

sympy.nextprime()

 sympy.nextprime(a, b) は a より大きな b 番目の素数を返します。

# PC_01-4

# 6より大きな4番目の素数
p = sympy.nextprime(6, 5)

print(p)
19

sympy.prevprime()

 sympy.prevprime(n) は n 以下の最大素数を返します。

# PC_01-5

# 30以下の最大素数
p = sympy.prevprime(30)

print(p)
29

sympy.primepi()

 sympy.primepi(n) は n 以下の素数の個数を返します。

# PC_01-6

# 30以下の素数の個数
pc = sympy.primepi(30)

print(pc)
10

sympy.isprime()

 sympy.isprime(n) は n が素数であるときは True, 素数でないとき (1 あるいは合成数であるとき) には False を返します。

# PC_01-7

# 12が素数であるかを判定
b1 = sympy.isprime(12)

# 29が素数であるかを判定
b2 = sympy.isprime(29)

print(b1, b2)
False True

sympy.randprime()

 sympy.randprime(a, b) は a 以上 b 未満のランダムな素数を返します。

# PC_01-8

# 100以上200未満のランダムな素数
rp = sympy.randprime(100, 200)

print(rp)
127

sympy.primorial()

 sympy.primorial(n) は n 番目までの素数の積 (素数階乗) を返します。

# PC_01-9

# 5番目までの素数の積(素数階乗)
# 2*3*5*7*11
q = sympy.primorial(5)

print(q)
2310

 

アルゴリズム図鑑 絵で見てわかる26のアルゴリズム

中古価格
¥2,011から
(2019/7/30 20:26時点)

合成数と素因数分解

 1 と素数を除く数を 合成数 (composite number) とよびます。
 合成数は必ず素数の積に分解 (素因数分解) されます。

sympy.composite()

 sympy.composite(n) は n 番目の合成数を返します。

# PC_02-1

import sympy

# 5番目の合成数
c = sympy.composite(5)

print(c)
10

sympy.compositepi()

 sympy.compositepi(n) は n 以下の合成数の個数を返します。

# PC_02-2

# 12以下の合成数の個数
cc = sympy.compositepi(12)

print(cc)
6

sympy.factorint()

 sympy.factorint(n) は n を素因数分解して、結果をディクショナリで返します。

# PC_02-3

# 23100を素因数分解
f = sympy.factorint(23100)

print(f)
{2: 2, 3: 1, 5: 2, 7: 1, 11: 1}

 この実行結果は、

23100 = 22・31・52・71・111

の形に素因数分解されたことを意味しています。