はじめに
いつもお世話になっております。
件名の解き方についてアドバイスを下さい。
これはCodeIQに投稿されていた問題だったのですが、どうしても解けませんでした。
結局解答のフィードバックなども無くどうやって解いたら良いのか困っています。
内容
今は閉じてしまって問題文すら読めなくなっていますがこんな感じの問題です。
素数の足し算で入力した値にいくつパターンがあるか出力してください(入力する素数の上限は100以下とする)
例は以下の通り
入力は以下のようにする
[最小値] [最大値] [和]
以下の場合だと2~19の間の素数の足し算で38になるパターンがいくつあるか出力する
2 19 38
19 + 17
3 + 5 + 11 + 19
2 + 3 + 5 + 11 + 17
なので答えは3
3
考え方
再帰を使うのだろうなと試してみましたがよく分からずに詰まっています。
因数分解ならなんとかなるんですがこれは難しすぎます。
考え方を教えてください。
C
1#if 0 2int getPrimeArray(int prime[]) { 3 int i, j; // counter 4 int num[25]; 5 6 // init 7 for (i = 0; i<ELMAX; num[i] = ++i); 8 9 // エラトステネスの篩(ふるい) 10 for (i = 0; i<ELMAX; i++) { 11 if (num[i] == 0) { 12 continue; 13 } 14 for (j = i + 1; j<ELMAX; j++) { 15 if (num[j] == 0) { 16 continue; 17 } 18 if (!(num[j] % num[i])) { 19 num[j] = 0; 20 } 21 } 22 } 23 24 // 配列に詰めていくよ 25 for (i = 1, j = 0; i<ELMAX; i++) { 26 if (num[i]) { 27 prime[j++] = num[i]; 28 } 29 } 30 return j; 31} 32#else 33 int prime[25] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 }; 34#endif 35 36 37 38 39int main() { 40 int imin, imax, ival; /* input */ 41 int tmp_val; /* temp */ 42 int min_el, max_el; 43 int i ; 44 45 // 標準出力からの入力は後回し 46 imin = 3; 47 imax = 19; 48 ival = 39; 49 50 // 51 tmp_val = (imax > ival)? ival : imax; 52 for (i = 0; _primenum[i] < tmp_val; i++); 53 max_el = i-1; 54 55 tmp_val = imin; 56 for (i = 24; tmp_val <= _primenum[i]; i--); 57 min_el = i; 58 59 printf("min[%d]=%d - max[%d]=%d\n", min_el, _primenum[min_el], max_el, _primenum[max_el]); 60 61 // 8(4+4) と 6(3+3) 以外の数は必ず解がある 62 63 return 0; 64}
回答4件
あなたの回答
tips
プレビュー