c言語 至急お願い致します

質問

10000以下の自然数のうち素因数分解を行ったときにその因子の数が最多となる数を求め，その数，因子の数，素因数分解の結果を表示するプログラムを作成して下さい．

出力形
8192 = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2
因子数：13

回答No.9

Tacosan

2 で割るのを忘れてました.

回答No.8

Tacosan

そうか, 考えてみれば
#include <stdio.h>
#include <stdlib.h>

int main()
{
int val = 1;
int factors, i;

for (factors = 0; (val *= 2) <= 10000; ++factors) {
;
}
printf("%d = 2", val);
for (i = 1; i < factors; ++i) {
printf(" * 2");
}
printf("\n因子数: %d\n", factors);

return EXIT_SUCCESS;
}
でいいのか.

本題とは全く関係ないのですが, 出力部分があやしい気がします＞#7.

符号なしなら d じゃなくて u だろとか uint64_t のフラグは l でいいのかとか.

あと, 実は g++ でも Windows だと危険だったりします.

回答No.7

hanabutako

> 素因数分解については理解できています
> なので10000を素因数分解するプログラムは作れるのですが、それ以下を判別して求めるプログラムは全くわかりません

と言うなら、まずはそのプログラムをどれかの補足に載せましょうよ。
素因数分解ができるなら、因子数もわかるでしょうから、あとはそれを比較する部分を書くだけです。

まずは素因数分解した時の因子数を数えるプログラムを書いてはいかがでしょうか。C言語で書くとしたら、素因数分解の結果を覚えておくメモリーの管理が面倒くさいはずなので、とりあえずそれは後回しにしましょう。
次に、因子数の最大値を求めるプログラムを書いてみましょう。
それから、後回しにしていた素因数分解した結果の記録と表示を作ってみましょう。
C言語で書くならなら、mainあたりで因子数が最大値を達成した時の値を覚えておく配列と各因数分解の時に使用する配列の2つを用意して、これまでの最大値を超える因子数が出るごとにコピーしておくとかになるでしょうね。長さを管理する変数をそれぞれに用意するか、それぞれの配列の最後に番兵として-1や0などを入れるかですね。(あるいは、単に2つ配列を用意し、作業用の配列を指すポインターとこれまでの最大値を超える因子数が出た時の配列を指すポインターを付け替えながら動作するか。)

10000以下の自然数なので、どんなに効率が悪いプログラムで現実的な時間で終わると思いますが、もしどうしても遅い場合は100などもう少し小さい数でプログラムを書いて、高速化方法を検討し、10000にチャレンジしましょう。
高速化で自分がまず思いつくのはエラトステネスの篩のように平方根までしか素因数分解のときに試さないというものです。
あと、再起を使ったプログラムを書いている場合、メモリーがある程度あり、メモリーの管理がかったるくないならメモ化も検討します。

ちなみに、以上のことをC++で書いてみるとこんな感じです。
#include <cmath>
#include <cstdio>
#include <unordered_map>
#include <vector>

using std::vector;
using std::printf;

std::unordered_map<uint64_t, vector<uint64_t> > memo;

vector<uint64_t>
factor(uint64_t num)
{
if (num < 2) { // i.e. 0, 1.
return vector<uint64_t>();
}

auto got = memo.find(num);
if (got != memo.end()) {
return got->second;
}

uint64_t max_div = static_cast<uint64_t>(std::sqrt(num));
for (uint64_t i = 2; i <= max_div; i++) {
if (num % i == 0) {
vector<uint64_t> result = factor(num / i);
result.push_back(i);
memo.emplace(num, result);
return result;
}
}
vector<uint64_t> ret;
ret.push_back(num);
memo.emplace(num, ret);
return ret;
}

int
main(void)
{
uint64_t max_value;
vector<uint64_t> max_factored;

for (uint64_t i = 2; i <= 10000; i++) {
vector<uint64_t> factored = factor(i);
if (factored.size() > max_factored.size()) {
max_value = i;
max_factored.swap(factored);
}
}

printf("%ld = ", max_value);
for (size_t i = 0; i < max_factored.size(); i++) {
if (i != 0) {
printf(" * ");
}
printf("%ld", max_factored[i]);
}
printf("\n#elms: %zd\n", max_factored.size());

return 0;
}

ちなみに、unordered_mapやautoを使っているので、C++11を理解しないコンパイラーだとコンパイルできません。-std=c++11をつけると対応したg++やclang++でコンパイルできると思います。

回答No.6

kmee

全部まとめてやろうとするから、わからなくなるのです。
「プログラム」を作ろうとするあら、わからなくなるのです。

・問題を細かくわけて考える
・まずは「やり方」を考える。その内容を「プログラミング言語で記述する」
というのがプログラミングのコツです。

素因数分解はできる、ということなら
1を素因数分解→因子数1→ 暫定最大値1,暫定最大因子数1
2を素因数分解→因子数1→ 暫定最大値1,暫定最大因子数1
3を素因数分解→因子数1→ 暫定最大値1,暫定最大因子数1
4を素因数分解→因子数2→ 暫定最大値4,暫定最大因子数2
5を素因数分解→因子数1→ 暫定最大値4,暫定最大因子数2
...
10000を素因数分解→因子数??→ 暫定最大値??,暫定最大因子数??
という「やり方」ができる、ということです。
これを「プログラミング言語で記述する」ことは簡単でしょう。

これでは効率が悪い、もっと効率よくしたい、という場合でも、まずは「やり方」を考えることです。
例えば
・素数は因子が1つしかないので最大値の候補とはならない
→最初に素数一覧を作れば、その一覧にあるものは候補から取り除ける
→効率のよい素数一覧作成方法は?
・8192=2^13で因子数13. log2(10000)=13.28....。ただの偶然でしょうか?

回答No.5

wormhole

1の素因数分解をする
2の素因数分解をする
...
10000の素因数分解をする

その中で一番因子の数が多かったのはどれ？

という問題なんですから素因数分解理解してるのならできるんじゃ？

回答No.4

επιστημη（@episteme）

> 素因数分解については理解できています
> なので10000を素因数分解するプログラムは作れるのですが

じゃ、それ見せて。

回答No.3

ts3m-ickw

素因数分解の方法と再帰プログラムの基本さえ判ってれば30分もかからないで作れるね。
参考になるようにPHPで書いてみた。C言語が読めるならPHPでも読めるでしょう。
でも面倒なので因子数の最大を求めてない。出力フォーマットも合わせてない。
あくまでも参考にしてくださいな。

<?php
function decomposition ($val, $div, $cnt) {
if ($val==0 || $val==1) print "因子数 $cnt\n";
else if ($val % $div ==0) {
$cnt ++;
print $div.",";
decomposition ($val/$div, $div, $cnt) ;
}
else decomposition ($val, $div+1, $cnt) ;
}

for ($i=10; $i<10001; $i++) {
print "$i,";
decomposition ($i, 2, 0);
}
?>

出力（一部抜粋）
8192,2,2,2,2,2,2,2,2,2,2,2,2,2,因子数 13

回答No.2

TooManyBugs

出来る人に１０万円くらい小遣いを渡して作ってもらいましょう。

回答No.1

hitomura

> プログラムを作成して下さい
嫌です。
あなたのこの質問は何らかの課題の丸投げにしか見えません。

別に課題だから答えないというのではありません。あなたが悩んでここまでしかできなかったというコードと一緒に質問されたならば、私たち回答者は（少なくとも私は）あなたが悩んでいることについて喜んでアドバイスするでしょう。
しかし、丸投げの質問に対して答をポンと渡すと結局はその当人のプログラミング技術の向上のためにならないことを、プログラミング系の回答者は実体験などから身に染みて実感しています。
だから、ことプログラミング関係の質問の場で課題の丸投げは嫌われますし、私も嫌いです。

あなたがこの課題に対してどんなコードが書けたかを補足願います。

補足

素因数分解については理解できています
なので10000を素因数分解するプログラムは作れるのですが、それ以下を判別して求めるプログラムは全くわかりません
アドバイスしていただけると幸いです