【プログラミング】

Question

fashion0208

23

21もっと見る

60pt

コンピュータ学習・教育

【プログラミング】

Nという数字の入力に対して、｛N-1, N-2, N-3, ..... 1｝の最小公倍数を求めるプログラミングを作成してください。
言語はCかPHPでお願いします。

（例）
入力：6　（　｛5, 4, 3, 2, 1｝の最小公倍数　）
出力：60

回答の条件

1人1回まで

登録：2008/08/20 19:53:21
終了：2008/08/20 21:01:17

※ 有料アンケート・ポイント付き質問機能は2023年2月28日に終了しました。

dev_zer0 2008/08/20 23:07:08

ちなみにC版、引数に数値を与えると結果が出力される
　
#include　<stdio.h>
　
int f(int n);
int lcm(int m, int n);
int gcd(int m, int n);

int main(int argc, char *argv[]) {
　　int n;
　
　　/* パラメータチェック */
　　if(argc != 2 || ((n = atoi(argv[1])) <= 0)) {
　　　　fprintf(stderr, "usage:%s number\n", argv[0]);
　　　　exit(1);
　　}
　
　　printf("ret:%d\n", f(n-1));
　　return 0;
}
　
/* この関数でハマった */
int f(int n)
{
　　int i, t = n;
　　for (i = 1; i < n; i++) {
　　　　t = lcm(t, i);
　　}
　　return t;
}
　
/* 最小公倍数を求める */
int lcm(int m, int n)
{
　　return m * n / gcd(m, n);
}
　
/* 最小公倍数を求める(ユークリッドの互除法) */
int gcd(int m, int n)
{
　　if (n == 0) return m;
　　return gcd(n, m % n);
}
　
f()関数の実装に悩んでたら先を越されてしまった．．．
fashion0208 2008/08/20 23:12:04

＞dev_zer0さん
有り難うございます。m(_ _)m
こんなに短時間に解いていただけるとは思っていなかったので、大変有り難いです。:)
Uプ 2008/08/21 02:02:05

これらのプログラムは
ｎと２の最小公倍数を求める
求められた物と次の数の最小公倍数を求める
をすべての数でやった物を表示する力任せの方法です

数学的な知識を使って，効率を上げることができそうです．

最小公倍数ですが，
それぞれの数（n-1,n-2,...,1)を素因数分解したときに現れる
それぞれの素因数における，最大の指数を調べ
すべての素因数の指数が調べた値の最大である数が，最小公倍数となる

例
2^3*3^2*7^1=336
2^1*3^3*5^2=1350
5^1*7^2*9^1=2205
この3つの数の最小公倍数は
2^3*3^3*5^2*7^2*9^1=2381400となる
（2の指数の最大値は336の3
　3の指数の最大値は1350の3
　5の指数の最大値は1350の2
7の指数、9の指数の最大値は１）
Uプ 2008/08/21 02:12:08

そこで、
n-1,n-2,...,1
これらの数をそれぞれ因数分解したときに発見される
それぞれの素数の指数の最大値を見つける方法ですが

たとえば、素数2の指数の場合ですが
純粋に、2のX乗がN未満かを調べる事で確認できます。

たとえば、
N=2000の時、１～１９９９を素因数分解したときにあらわれる
2の指数の最大値ですが
2＾10＝1024で、１０は含まれて、2^11=2048で11は含まれないので
2の指数の最大値は10であることがわかります
同様に
3^6=729で、3^7=2187なので、3の指数の最大値は6であることがわかります
同様に、1999までに現れるすべての素数について
指数の最大値を計算し
2^10*3^6*5^A*7^B*...
としていけば、最小公倍数を求めることができるはずです
Uプ 2008/08/21 02:25:02

とりあえず、とっさに思いついた方法だけで＾＾；

int fanc(int n){
int result=1;
int t;

//n-1までの素数列を得る（中身は略）
list sosu = get_sosu(n-1);

while(sosu->next != NULL){
sosu=sosu->next;
t = sosu->val;
while(t < n){
result *= sosu->val;
t *= sosu->val;
}
}
return result;
}
dev_zer0 2008/08/21 04:10:39

> 素因数分解
ここで質問してよいのかどうか不明なのですが、
私の知っている限り、「簡単に」素因数分解できるアルゴリズム、
「簡単に」ある数値が素数であるかを判定するアルゴリズムは無いはずです
もし存在するならば、現在の暗号化技術が根底から覆されます
# 今の暗号化技術は大きな数の素因数分解や素数判定は
# 簡単に求めることが出来ないことを前提とされています
　
多分、素数を求める最も素朴なアルゴリズムは
「エラトステネスのふるい」ですけど、
その場合も力任せで素数を抽出していて、
それだけで私が書いたCソースに匹敵する量があるはずです
　
どちらがよりエレガントなんでしょうか？
# 素数判定してくれる標準関数がある言語があればいいんですが
# C, PHP共にそんな標準関数は無いはずです
Uプ 2008/08/21 13:06:58

＞dev_zer0さん

＞素因数分解
確かに、「大きな数」を「簡単に」素数かどうかを判定するのは難しいというのはよく聞きますが、
「大きな数」というのは、何十桁もある数であって、
そのような数になった場合、扱う数も巨大になり、
すべての数での最小公倍数を一つ一つ計算していくのもまた大きな手間になります

（ちなみにプログラム中では素因数分解はしません）

素数列抽出は、私は「エラトステネスのふるい」のアルゴリズムぐらいしか知りませんが
最小公倍数や最大公倍数を求めるアルゴリズムよりはソース量があったはずです
ソース量は多くなりますが、効率よく計算できるかもと思って提案してみました

計算量の計算は苦手で、客観的判断はできないのですが・・・＾＾；

＞標準関数
標準関数があったとしても、その関数が多くの計算をするはずなので
ソースは短くなったとしても、計算量は減らなさそうです
fashion0208 2008/08/21 13:18:46

>dev_zer0さん、upuさん
色々と有り難うございます。

現状、入力値Nが100未満ということが分かっているので、
リスト化したりして使うことにしました ^^;

確かに数字が10万とか100万になると計算がしんどくなりそうですね。。。
dev_zer0 2008/08/21 14:05:31

> upuさん
なるほど、計算量として考えると合理的かもしれません
入力値が100未満という前提ならば、提示してもらったプログラム中の
list sosuの中に予め100未満の素数を突っ込んでおくとかすると
かなりエレガントなプログラムになりそうですね

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

リクエスト送信済

回答リクエストを送信したユーザーはいません

pahoo · Accepted Answer · 2008-08-20T20:56:01+09:00

PHPで書いてみました。

力任せですが、hoge が目的の値を求める関数です。

引数のエラーチェックは一切行っていませんのでご注意を。

//最大公約数
function gcd($x, $y) {
    if ($y == 0)    return $x;
    else            return gcd($y, $x % $y);
}

//最小公倍数
function lcm($x, $y) {
    return $x * $y / gcd($x, $y);
}

//目的の関数
function hoge($n) {
    $y = $n;
    for ($m = 1; $m < $n; $m++) {
         $y = lcm($y, $m);
    }
    return $y;
}

【プログラミング】

ベストアンサー

pahoo59606332008/08/20 20:56:01

コメント（9件)

この質問への反応（ブックマークコメント）