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

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

素数

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

素数判定プログラム

 ループ処理や条件分枝、breakキーワードを駆使して素数判定プログラムを書いてみます。素数は 1 と自身以外に約数をもたない数と定義されているので、N を

  2, 3, 4, ... N-1

の順に割って、どの数でも割り切れなければ、N は素数であることになります。これが最も素朴な手法なのですが、初等整数論の定理によって、除数(割る数)の上限値は √N の整数部分でよいことがわかっています(これによって計算回数を大幅に節減することができます)。たとえば N = 24 であれば、

  √24 = 4.8989794 ......

なので、除数の上限値は 4 となります。しかし、下のサンプルコードでは除数 k のとりうる範囲を 1 つだけ多くして 2 ~ ct + 1 としてあります。すなわち Range関数 の引数は (2, ct + 2) となります。1 は素数ではないので、1 が入力された場合は if文の条件式で除外する必要があります。しかし、ct の値は √1 = 1 なので、range関数の引数が (2, 2) となってしまいます。これでは rangeオブジェクトの要素数が 0 となってループ処理には使えません。1 が入力された場合の処理を別の行に書いてもいいのですが、そうするとコードの行数が増えてしまうので、1行の if文にまとめておきました。

# 素数判定プログラム

# sysモジュールをインポート
import sys

my_msg = "正の整数を入力してください:"

# ユーザーが値を入力
x = input(my_msg)

# x を整数型に変換
x = int(x)

# x が正の値でなければプログラムを終了
if x <= 0:
    print(my_msg)
    sys.exit()

# 除算の上限値を設定
ct = int(x**0.5)

for k in range(2, ct + 2):
  # x が 1 または k で割り切れる場合
    if x == 1 or x % k == 0:
        print(x, "は素数ではありません。")
        break
else:
    print("{}は素数です".format(x))
正の整数を入力してください:19
19は素数です

 コードを実行すると数字の入力が促されるので、適当な値を入力してください。
 たとえば 19 を入れると「 19 は素数です」と返ってきます。

 コードの 1 行目で sys モジュールをインポートしてありますが、これはユーザーが負の値や 0 を入力したときに、sys.exit() によってプログラムを終了させるためです。
 

sympy.primerange()

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

# SYMPY_PRIME_NUMBER_01-1

import sympy

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

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

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

# SYMPY_PRIME_NUMBER_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 番目の素数を返します。

# SYMPY_PRIME_NUMBER_01-3

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

print(p)
11

sympy.nextprime()

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

# SYMPY_PRIME_NUMBER_01-4

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

print(p)
19

sympy.prevprime()

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

# SYMPY_PRIME_NUMBER_01-5

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

print(p)
29

sympy.primepi()

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

# SYMPY_PRIME_NUMBER_01-6

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

print(pc)
10

sympy.isprime()

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

# SYMPY_PRIME_NUMBER_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 未満のランダムな素数を返します。

# SYMPY_PRIME_NUMBER_01-8

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

print(rp)
127

sympy.primorial()

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

# SYMPY_PRIME_NUMBER_01-9

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

print(q)
2310

 

Pythonデータサイエンスハンドブック ―Jupyter、NumPy、pandas、Matplotlib、scikit-learnを使ったデータ分析、機械学習

新品価格
¥4,536から
(2019/10/24 18:17時点)

合成数と素因数分解

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

sympy.composite()

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

# SYMPY_PRIME_NUMBER_02-1

import sympy

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

print(c)
10

sympy.compositepi()

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

# SYMPY_PRIME_NUMBER_02-2

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

print(cc)
6

sympy.factorint()

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

# SYMPY_PRIME_NUMBER_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

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