Pythonコミュの1から２０までのすべての整数で割れる最小の数

http://projecteuler.net/index.php?section=problems&id=5

上のサイトにある問題です。(英語)
1から20までのすべての整数で割り切れる最小の数を導き出すために、下のコードを書いたんですが、どうも、無限ループみたいになってしまいます。

よろしければ、python hackerの方、ヒントをお願いします。
(mixiのせいで、インデントがまずいと思いますが、よろしくお願いします。)

##########################
x = 0
n = 20*19 - 1
z = 0

while x != 1:
(インデント1つ) z = 0
(インデント1つ） n = n + 1

(インデント1つ） for y in range (1, 21):

（インデント2つ） if n%y == 0:

（インデント3つ） z = z + 1

（インデント1つ）if z == 20:
（インデント2つ） x = 1

print n
##############################

コメント(24)

最初
全て
最新の40件

[1] mixiユーザー 06月04日 21:49

# こんなんでどうでしょ？
import sys

cnt = 1;
while True:
　　 if cnt % 1000000 == 0:
　　　　 print "...", cnt;
　　 for i in range(1,21):
　　　　 if cnt % i != 0:
　　　　　　 break;
　　　　 if i == 20:
　　　　　　 print "Ans >>", cnt;
　　　　　　 sys.exit();
　　　　
　　 cnt-=1;

[2] mixiユーザー 06月04日 22:23

こんなのでどうでしょ？

reqv=20
for v in range(20-1,1,-1):
　if reqv % v != 0:
　　reqv *= v
print reqv

[3] mixiユーザー 06月04日 22:38

# こんなのもかいてみました。結構苦労した。。。
def fact(num, n):
　　 if n == 1:
　　　　 return True;
　　 else:
　　　　 if num % n == 0:
　　　　　　 return fact(num, n-1);
　　　　 else:
　　　　　　 return False

cnt = 2432902007943847440;
while True:
　　 if fact(cnt, 20):
　　　　 print "Ans >>", cnt;
　　　　 #break;
　　 cnt -= 1;

[5] mixiユーザー 06月04日 23:14

私も上のサイトに登録して、今１７問解いたところです。
この問題は、プログラミングと言うより数学に近いですね。
私は掛け算だけ書いてその結果をPythonで導いてしまいました。

単発質問トピを立てるよりも、「初心者質問トピ」で聞くほうが嬉しいかも。＞スーピンさん

[7] mixiユーザー 06月05日 05:24

やっぱり、人のコードを直すより、自分で考えた方が早いですか…

＞ロボ平さん

すいません。早くヒントが欲しいあまりに、単発で立ててしまいました。次から初心者トピで聞きます。

17問達成はすごいですね！ランキングはどの辺ですか？

僕は4問しか解けていません。

[8] mixiユーザー 06月05日 05:56

確認してみましたが、

ケースケさんともろおさんの答えは正解ではないようです。

[9] mixiユーザー 06月05日 07:18

解けました。IDLEは使いましたが、プログラミングしませんでした。

やっと五問！

[10] mixiユーザー 06月05日 10:21

というか、サイト名が数学ですよね(^^;;

1から20なら手作業でもしれてますが、これを 1 から N (N >=2 の自然数)とすると、プログラミングが必須です。

エラストテネスのふるいで素数を求める方法を0,1じゃなくて、カウントしてあげればいいと思います・・・というか・・・
N 以下の素数リストPの各要素に対してP[i]**M(Mは自然数) が N以下であるMの最大値を求めて、各要素に対してM乗した結果の積を求めればいいのかな？

[11] mixiユーザー 06月05日 12:47

＞1から20なら手作業でもしれてますが、これを 1 から N (N >=2 の自然数)

1～20でもかなり大きい数だったので、これが1～50だった暁には､コンピューターじゃ扱えない数の大きさになるかと思います｡

Mathematicaだったら大丈夫なんですかね｡

[12] mixiユーザー 06月05日 12:56

Pythonで計算可能だと思われますよ。
50!が扱えるので。

for i in range(1,51):
　　 cnt*=i

[14] mixiユーザー 06月05日 19:42

答えは232792560ではないのですか？
恐らくけーすけさんのであってると思うのですが･･･

[15] mixiユーザー 06月05日 20:53

スーピンさんのも合ってるような。ただ1.8GHzのCeleronで65分ほどかかりましたが(^_^;)。
ちょっと手を入れて

n = 20 * 19 - 1
while True:
　z = True
　n = n + 1
　for y in range(1, 21):
　　if n % y != 0:
　　　z = False
　　　break
　if z:
　　break
print n

とすると半分以下の時間で終わりました。

[16] mixiユーザー 06月05日 21:00

自分もここの書き込み見てはじめてみました。
この問題に関しては自分もロボ平さんと同じく
手作業で解きました。
jackさんの言うとおり、Nより小さい素数の冪
で一番大きくなるものを掛けていけば、ほかの数は
自動的に割り切れるようになるので、
たとえば、50以下なら
32 * 27 * 25 * 49 * 11 * 13 * (残りの素数全部
とやれば、50以下の場合もたぶん手作業でＯＫ

[17] mixiユーザー 06月05日 22:09

とぴをまちがえてポストしたorz.
んで投稿しなおし。

> スーピンさんのも合ってるような。
> ただ1.8GHzのCeleronで65分ほどか
> かりましたが(^_^;)。

そんなにきつい計算じゃないと思います・・・。
夕食食べながらへろへろときました。
コーディング時間こみでそれより短いです。

実行時間ははかる必要も無いぐらいみじかいです。環境は2年ちかく前に買ったdell inspiron6000です。

実行結果
D:\work\python\quiz>python divisible_n.py
{2: 1}
{2: 2, 3: 2}
{2: 4, 3: 2}
{17: 1, 3: 1, 5: 1}
{2: 8}
2
6
12
2520
232792560
3099044504245996706400
69720375229712477164533808935312303556800

[18] mixiユーザー 06月05日 22:18

手で解ける問題がそんなに時間かかるなんて変じゃないですか。手でやっていることをそのまま実装すればいい・・・。

ちょっとどんなコード書いているか手を止めて考えませんか・・・。
http://ja.wikipedia.org/wiki/%E8%A8%88%E7%AE%97%E8%A4%87%E9%9B%91%E6%80%A7%E7%90%86%E8%AB%96

[19] mixiユーザー 06月05日 22:21

間違ってたので再度。

import math

nx=20
for m in range(19,1,-1):
　if nx % m != 0:
　　nnx=nx
　　nm = m
　　i = 2
　　while i < math.sqrt(nm):
　　　if (nm % i) == 0 and (nnx % i) == 0:
　　　　[nm,nnx] = [x/i for x in [nm,nnx]]
　　　　continue
　　　i+=1
　　nx *= nm
print nx

[20] mixiユーザー 06月05日 23:01

> 1から20までのすべての整数で割り切れる最小の数を導き出す

問題の意味を取り違えていたら申し訳ないのですが，以下のようなコードでいかがでしょうか？

def gcd(m,n):
　　if n==0:
　　　　return m;
　　return gcd(n,m%n);

def lcm(m,n):
　　return m*n/gcd(m,n);

def lcm1toN(n):
　　if n==1:
　　　　return 1;
　　return lcm(lcm1toN(n-1), n);

実行すると，
>>> lcm1toN(10)
2520
>>> lcm1toN(20)
232792560L

のようになります．

[21] mixiユーザー 06月06日 01:18

> 20: Freedomさん
答えあってますよ。プログラムも見事ですね。

[22] mixiユーザー 06月06日 01:58

> 20. Freedom
エレガントで本質的な答えですね。

[24] mixiユーザー 06月06日 09:55

>かぜはるかさん

あのコードで答え出ますか｡65分はかかりすぎですね｡

もっと精進したいと思います｡

ログインすると、残り4件のコメントが見れるよ