指定した自然数のうち約数が指定した数あるか求める計算をはやくしたい

Question

前提・実現したいこと

指定した自然数（max）のうち約数が指定した数（hit）ある計算をするプログラムを作りました。
ですが、とても遅いと感じもっとはやくできないのかと思いました。

該当のソースコード

import sys, time

max = 114514
count = 0
count1 = 0
hit = 13
seikai = []

start = time.time()
print(str(max) + "つのうちの、約数が" + str(hit) + "つある数を調べます")

def keisan():
    global count
    global count1
    count += 1
    for i in range(1,count):
        if count % i == 0:
            count1 += 1

while not count == max:
    if not count1 == hit - 1:
        print(str(count) + "は" + str(count1) + "のため再計算します")
        count1 = 0
        keisan()
    else:
        print(str(count) + "は正解です")
        seikai.append(count)
        count1 = 0
        keisan()
else:
    if not seikai:
        print("正解はありませんでした")
    else:
        elapsed_time = time.time() - start
        print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")
        print("終了しました\n以下が正解です" + str(seikai))

試したこと

Numbaを使用しようとしましたが、global変数を使っているためエラーが出てだめでした。

前提として、Python3でお願いします。何か無駄な部分等あればご教授よろしくお願いいたします。

Comments

[LouiS0616]

『素数が指定した数ある』と『約数が指定した数ある』のどちらが正しいのですか？

[TanakashiXr]

申し訳ございません。
約数に修正しました。

Answer 1

約数の個数が 13 （奇数) ということから、 平方数だけをしらべればよいことになります。
( n に対して p が 約数なら、 n / p も 約数になる。
約数の個数が奇数になるのは p = n / p. つまり n = p * p のかたちのときだけ)

このことを治療して、プログラムしてみました。
探す範囲も広げてみました。

c2.py

import time
import math

def is_squre(num):
    sqrt =int(math.sqrt(num))
    return num == sqrt * sqrt

def keisan(num):
    d = [1, num]
    for i in range(2, 1 + int(math.sqrt(num))):
        if num % i == 0:
            d += [i, num // i]
    return len(set(d))

max = 999999999999 # 114514
hit = 13
seikai = []

print("1 .." + str(max) + " 中の約数が" + str(hit) + "つある数を調べます")

start = time.time()

if hit == 1:
    # 約数の個数が 1 なのは 1 だけ
    seikai = [1]
else:
    # 約数の数が奇数なのは、平方数に限る
    seikai = [num for num in range(2, int(math.sqrt(max)) + 1) if is_squre(num) and keisan(num) == hit]

elapsed_time = time.time() - start
print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

if not seikai:
    print("正解はありませんでした")
else:
    print("終了しました\n以下が正解です" + str(seikai))
    print(len(seikai))

実行例

参考情報

• 数の性質 4096

https://ja.numberempire.com/4096

• 数の性質 531441

https://ja.numberempire.com/531441

Answer 2

global変数を使った時に、エラーがでてだめならば、global変数を除去してみてはいかがでしょうか?　上記のプログラムでcountとcount1をglobal変数にもたせておく必要性は特に無いかなと思いました。

countは、約数の数を調べるターゲットとなる数、count1は、countの約数の数だと思いますが、それぞれ、countは引数として関数に渡して、count1は、戻り値として元の処理に返してしまえば、いいと思います。

参考までに、numbaを使って、以下のように書きなおしてみました。(print文の箇所は大量に出力されると困るので、一部コメントアウトしています。)

import sys, time, numba

max = 114514
hit = 13
seikai = []

start = time.time()
print(str(max) + "つのうちの、約数が" + str(hit) + "つある数を調べます")

@numba.jit
def keisan(count):
    count1 = 0
    for i in range(1,count):
        if count % i == 0:
            count1 += 1
    return count1

count = 0
count1 = 0
while not count == max:
    count1 = keisan(count)
    if not count1 == hit - 1:
        # print(str(count) + "は" + str(count1) + "のため再計算します")
        pass
    else:
        # print(str(count) + "は正解です")
        seikai.append(count)
    count += 1
else:
    if not seikai:
        print("正解はありませんでした")
    else:
        elapsed_time = time.time() - start
        print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")
        print("終了しました\n以下が正解です" + str(seikai))

余談ですが、約数を数える上でのトリックとして、1〜countの値全ての数について割り切れるかどうかを判定する必要はありません。count/2+1〜count-1までの範囲には、countの約数は存在しないので、この範囲の値については調べなくても良いのです。

1 -> 1
2 -> 1, 2
3 -> 1, 3
4 -> 1, 2, 4
5 -> 1, 5
6 -> 1, 2, 3, 6
...
12 -> 1, 2, 3, 4, 6, 12
13 -> 1, 13
14 -> 1, 2, 7, 14
15 -> 1, 3, 5, 15
16 -> 1, 2, 4, 8, 16

などと、書いていけば分かると思いますが、基本的に2で割り切れた場合、その数の自分自身を除いく最大の約数は、2で割った値になります。また、2で割り切れなかった場合も、2で割った値を四捨五入した値以上の約数になることは、約数の性質上ありえません。

なので、実は、keisanの処理の箇所は以下のように書きなおす事ができます。

def keisan(count):
    count1 = 0
    for i in range(1,int(count/2) + 1):
        if count % i == 0:
            count1 += 1
    return count1

さらにこの辺の約数の性質を上手く使うと、さらに効率よく約数を求めていく処理が書けると思います。この辺の高速化の処理を考えてみるのも面白いと思いますので、是非チャレンジしてみてください！

Comments

[TanakashiXr]

global変数の除いてnumbaを使ったサンプルにして約６倍になりました！
ありがとうございました！高速化に向けて頑張りたいと思います！

Answer 3

全体を書き直してみました。
そして質問にあるコードの途中の print 文を削除、最後に seikai の個数を出すようにしたものと速度を比較してみました。

c1.py

import time
import math

def keisan(num):
    d = [1, num]
    for i in range(2, 1 + int(math.sqrt(num))):
        if num % i == 0:
            d += [i, num // i]
    return len(set(d))

max = 114514
hit = 13
seikai = []

print("1 .." + str(max) + " 中の約数が" + str(hit) + "つある数を調べます")

start = time.time()

if hit == 1:
    # 約数の個数が 1 なのは 1 だけ
    seikai = [1]
else:
    seikai = [num for num in range(2, max + 1) if keisan(num) == hit]

elapsed_time = time.time() - start
print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

if not seikai:
    print("正解はありませんでした")
else:
    print("終了しました\n以下が正解です" + str(seikai))
    print(len(seikai))

20000 までの場合と、114514 までの場合で処理時間を比較してみました。

実行例