質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Q&A

解決済

2回答

3827閲覧

pythonで最小公倍数を求めるプログラムの速度を上げる方法を教えてください。

malia

総合スコア9

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

0グッド

1クリップ

投稿2019/09/27 14:38

前提・実現したいこと

タイトル通りです。
また、初心者のためおすすめの変数名やこうした方がいいなどのテクニックなど教えていただけたら大変大変ありがたいです。

'''
Problem 5 「最小の倍数」 †
2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.

では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.
'''

該当のソースコード

python

1import sys 2 3count = 11 4current = 20 5 6while True: 7 for i in range(1, current+1): 8 if count%i : 9 break 10 else : 11 print( count ) 12 sys.exit() 13 count += 1

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

20×19×9 (18/2) ×…
を計算していくのが早そうです。
つまり、
20, 19,18…と見ていくのですが、
最初は20
→次は19 (19は今まで出てきた数の約数で割り切れない)
→次は9 (18は20の約数2で割り切れる)
→次は17(17は今まで出てきた数の約数で割り切れない)
→…

投稿2019/09/27 14:53

gnbrganchan

総合スコア438

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

ベストアンサー

結論をいうとこれでできます。(Python >= 3.5)
Python3.4の場合はgcd(最大公約数)モジュールはmathではなくfractionにあるので注意です。

python

1import math 2 3ans = 1 4for i in range(2, 21): 5 ans = ans * i // math.gcd(ans, i) 6print(ans)

まず、ans * i // math.gcd(ans, i)はansとiで割り切れる数、すなわち最小公倍数を計算します。
1と2の最小公倍数を求め、その数と3の最小公倍数を求め、さらにその数と4の...とやっているうちに、1から20までの最小公倍数をもとめることができます。

投稿2019/09/27 14:50

編集2019/09/27 14:51
fukatani

総合スコア626

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

fukatani

2019/09/27 14:52

最大公約数はユークリッドの互除法というアルゴリズムで求めると高速ですが、Pythonならgcd関数を叩けば内部でやってくれます。
malia

2019/09/27 17:58

ありがとうございます 一瞬で計算が終わりました 数学的な理由がわかりませんが大体の動きはわかりました。 あとは調べてみます。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問