1

私は現在、「1 から 20 までのすべての数で割り切れる最小の正の数は?」という問題を解決しようとしています。

これまでのところ、動作するように見えるコードを作成しましたが、非常に長い時間がかかります。さらに、if 内で膨大な量の「and」ステートメントを使用する必要がありますが、これは非常に効率的でも専門的でもないようです。

このコードを最適化し、より整頓するにはどうすればよいでしょうか?

number = 1
result = 0

def divide(candidate):
    if candidate % 2 == 0 and candidate % 3 == 0 and candidate % 4 == 0 and candidate % 5 == 0 and candidate % 6 == 0 and candidate % 7 == 0 and candidate % 8 == 0 and candidate % 9 == 0 and candidate % 10 == 0 and candidate % 11 == 0 and candidate % 12 == 0 and candidate % 13 == 0 and candidate % 14 == 0 and candidate % 15 == 0 and candidate % 16 == 0 and candidate % 17 == 0 and candidate % 18 == 0 and candidate % 19 == 0 and candidate % 20 == 0:
        global result
        result = 1
        return 1

    else:
       global number
        result = 0
        number = number + 1
        return 0

while result == 0:
divide(number)

print "The lowest number divisible by all integers between 1-20 is:", number

明確にするために、これは宿題ではありません。私は独学で Python を学んでおり、その一環として ProjectEuler の問題をいくつか試しています。

4

4 に答える 4

9

あなたの問題はコンピュータの助けを借りずに簡単に解決できるので、最適化されたバージョンは単に答えを印刷するでしょう。どの程度の最適化が許容できると考えるかを判断するのは少し難しいです。

コンピューターなしでこの質問を解決する方法は次のとおりです。1から20までのすべての数で割り切れる最小の数は、これらの数の中で発生するすべての素数冪で割り切れる必要があります。一方、この範囲のすべての素数冪で割り切れる数がある場合、1から20までのすべての数で割り切れるでしょう。異なる素数の素数冪はコプライムであるため、すべての最高の素数冪の積です。この範囲の各素数が答えになります。最適化されたコードは次のとおりです。

print 2**4 * 3**2 * 5 * 7 * 11 * 13 * 17 * 19
于 2012-04-10T17:40:52.990 に答える
2

あなたは前の数の要因である数を排除することから始めることができます。4で割り切れるすべての数値は2で割り切れます。10で割り切れるすべての数値は5で割り切れます。9で割り切れるすべての数値は3で割り切れます。

于 2012-04-10T17:38:23.970 に答える
0

ここで非常に単純ですが非常に効率的なのは、素数とその累乗のみを使用することです。なぜあなたは彼らの掛け算を考えなければならないのですか？「and」条件を4,9,16,5,7,11,13,17,19だけに減らします

于 2012-04-10T17:38:15.227 に答える
0

私の場合は、素数を「mod」（％）しようとします。1から20までのすべての数字を使用するわけではありません。

于 2012-04-10T17:40:20.650 に答える