「素数の足し算で」の解き方を教えてください

Question

はじめに

いつもお世話になっております。
件名の解き方についてアドバイスを下さい。

これはCodeIQに投稿されていた問題だったのですが、どうしても解けませんでした。
結局解答のフィードバックなども無くどうやって解いたら良いのか困っています。

内容

今は閉じてしまって問題文すら読めなくなっていますがこんな感じの問題です。

素数の足し算で入力した値にいくつパターンがあるか出力してください(入力する素数の上限は100以下とする)

例は以下の通り

入力は以下のようにする

[最小値] [最大値] [和]

以下の場合だと2～19の間の素数の足し算で38になるパターンがいくつあるか出力する

2 19 38

19 + 17
3 + 5 + 11 + 19
2 + 3 + 5 + 11 + 17

なので答えは3

3

考え方

再帰を使うのだろうなと試してみましたがよく分からずに詰まっています。
因数分解ならなんとかなるんですがこれは難しすぎます。
考え方を教えてください。

#if 0
int getPrimeArray(int prime[]) {
	int i, j; // counter
	int num[25];

	// init
	for (i = 0; i<ELMAX; num[i] = ++i);

	// エラトステネスの篩（ふるい）
	for (i = 0; i<ELMAX; i++) {
		if (num[i] == 0) {
			 continue;
		}
		for (j = i + 1; j<ELMAX; j++) {
			if (num[j] == 0) {
				continue;
			}
			if (!(num[j] % num[i])) {
				num[j] = 0;
			}
		}
	}

	// 配列に詰めていくよ
	for (i = 1, j = 0; i<ELMAX; i++) {
		if (num[i]) {
			prime[j++] = num[i];
		}
	}
	return j;
}
#else
	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 };
#endif




int main() {
	int imin, imax, ival;	/* input */
	int tmp_val;			/* temp */
	int min_el, max_el;
	int i ;

	// 標準出力からの入力は後回し
	imin = 3;
	imax = 19;
	ival = 39;

	// 
	tmp_val = (imax > ival)?  ival : imax;
	for (i = 0; _primenum[i] < tmp_val; i++);
	max_el = i-1;

	tmp_val = imin;
	for (i = 24; tmp_val <= _primenum[i]; i--);
	min_el = i;

	printf("min[%d]=%d - max[%d]=%d\n", min_el, _primenum[min_el], max_el, _primenum[max_el]);

	// 8(4+4) と 6(3+3) 以外の数は必ず解がある
	
	return 0;
}

Comments

[A.Ichi]

上記のケースの4つの素数組み合わせでは、他に2個有りますが、これらは対象ではないのでしょうか？ 3 + 5 + 11 + 19 = 38、 3 + 7 + 11 + 17 = 38、 3 + 5 + 13 + 17 = 38

19 + 17 = 36 です。

Answer 1

ヒントだけですが。

38 = 2 * 19がありませんね?
つまり、同じ素数は使わない、という条件がこの問題にはあります。

2を使わない、3を使わない、5を使わない、…
2を使う、3を使わない、5を使わない、…
2を使わない、3を使う、5を使わない、…
…

こんな感じで、全部の組合せを調べて条件を満たす組合せの数を数えれば答えられます。
計算量は高々2^25回のループです。

数がもっと大きいと、別のアルゴリズムが必要になります。(思いついたら追記します。)

思いついたので追記：38で例示します。

38-37 = 1
1は37未満の素数の組で書けない
38-31 = 7 (ok)
7-5 = 2
∴ 38-31-5 = 2 (ok)
2は5未満の素数の組で書けない。
7-3 = 4
4-2 = 2
2は2未満の素数の組で書けない
…

再帰を使えばこんな風に書けます。分解したい整数、分解に使える素数の最大値・最小値を関数に渡しましょう。

Comments

[kuma_dansyaku]

回答ありがとうございます。
参考になりました。

[kuma_dansyaku]

～

Answer 2

アルゴリズムの問題は知らないと見当もつかない事がありますよね。
この内容でしたら、
1.初めから2~97までの素数列を用意する（配列など）

2-a.入力に応じて素数列を編集する（例えば、2から19までの素数列にする）
3-a.再帰関数を実行する

2-b.再帰関数の終了条件に、素数が入力で指定された範囲内に入っているかを判断する条件分岐を入れる（ソースでいえばp[i]<imin または p[i]>imax）

の２パターンが思いつきます。
Cのソースはパターンb, C++のソースはパターンaで作りました。
Cの再帰関数funcの動作については、ほとんどmajiponiさんの説明のとおりです。
"素数の和がsumになる組み合わせを探す"、という処理を"sumから素数を引いた結果が0になる組み合わせを探す"という処理に変えています。これは別にどちらでもいいと思います。
再帰関数を使うときは終了条件をどうするのか、求めたい値を外部変数に保存するのか、返り値にするのかを考えられると使えるようになるんじゃないかと思います。

最後に

入力が 2 19 38 の場合の答えは 6 になると思います。
再帰関数は深さ優先探索と幅優先探索の勉強をするといいと思いますよ。
頑張ってください！

以下、ソースコード

#include "stdio.h"

int p[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 };
int imin, imax, ival;    /* input */

int func(int sum, int i){
    if(p[i]<imin) return func(sum,i+1); // 素数が最小値未満なのでインデックスをすすめる
    if(sum==0) return 1; // 和が０なのでこの組み合わせは成功だった
    if(sum<0) return 0; // 和が負になったのでこの組み合わせは失敗だった
    if(p[i]>imax) return 0; // 素数が最大値より大きいので失敗。
    return func(sum-p[i],i+1)+func(sum,i+1); // 現在のインデックスの素数p[i]をsumから引いた場合と引かなかった場合のそれぞれについて計算する。
}

int main() {
    int i ;

    // 標準出力からの入力は後回し
    imin = 2;
    imax = 19;
    ival = 38;
    // scanf("%d%d%d", &imin,&imax,&ival);
    
    printf("%d",func(ival,0));
    
    return 0;
}

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

int minn,maxn,sum;
vector <int> p;

// エラトステネスの篩 グローバル変数バージョン
void prime(int n){
  vector <bool> arr(n);
  fill(arr.begin(),arr.end(),true);
  arr[0]=false;
  arr[1]=false;
  for(int i=2; i<sqrt(n); i++){
    if(arr[i]){
      for(int j=2; i*j<n; j++){
        arr[i*j]=false;
      }
    }
  }
  for(int i=2; i<n; i++){
    if(arr[i]){
      p.push_back(i);
    }
  }
  if(arr[91])cout << "91" << endl;
}
// 2~97までの素数を必要な分だけにする
void slice_prime(){
	vector <int> temp = p;
	p.clear();
    for(int i=0; i<temp.size(); i++){
        if(temp[i]>=minn&&temp[i]<=maxn)p.push_back(temp[i]);
    }
}

// 再帰関数。2から順番に素数をsumから引いた場合と引かなかった2つの場合について再起を行う。
// 終了条件はsumが０（丁度和がsumになった場合）とsumが負（和がsumにならなかった場合）、そしてインデックスiがvector pのサイズを越えた（最大素数maxnのインデックスを越えた）とき。
int func(int sum, int i){
    if(sum==0) return 1;
    if(sum<0) return 0;
    if(i==p.size()) return 0;
    return func(sum-p[i],i+1)+func(sum,i+1);
}


int main() {
    // 入力
    cin >> minn >> maxn >> sum; cin.ignore();
    // 素数生成
    prime(100);
    // 素数をminn以上maxn以下のものだけにする
    slice_prime();
    // 再帰関数を実行する
    cout << func(sum,0) << endl;
    return 0;
}

Comments

[kuma_dansyaku]

回答ありがとうございます。
頂いたソースを見てここまでシンプルになるんだ驚いています。
A.Ichiさんのソースと共に再帰を使ったアプローチはとても参考になりました。
教えて頂いた深さ優先探索と幅優先探索を検索して勉強いたします。

Answer 3

順列組み合わせのプログラムのパターンを使って計算した結果で [和]と同じになるものを表示しています。

#include <stdio.h>
#define MAX 100
#define N 16
int prms[48]={0};
int k=0;
int buffer[N];

int prime_make(int prms[])
{
  int i,j,yaku;
  for(i=1;i<=MAX;i++){
    yaku=0;
    for(j=1;j<=i;j++){
      if(i%j==0) yaku++;
    }
    if(yaku==2) prms[k++]=i;
  }
  return k;
}

void print_combination(int n, int a)
{
  int i,j;
  j=0;
  for (i = 0; i < n; i++){
    j+=prms[buffer[i]-1];
  }
  if (j==a){
      for (i = n-1; i >= 0 ; i--)
        printf("[%d]",prms[buffer[i]-1]);
    printf("\n");
  }
}

void comb_sub(int n, int r, int m, int a)
{
  int i;
  if (r == 0)
    print_combination(m, a);
  else if (n == r) {
    for (i = r; i > 0; i--)
      buffer[m++] = i;
    print_combination(m, a);
  } else {
    comb_sub(n - 1, r, m, a);
    buffer[m] = n;
    comb_sub(n - 1, r - 1, m + 1, a);
  }
}

void combinations(int p, int q, int a, int r)
{
  int n=q-p+1;
  if (r > 0 && r <= N) comb_sub(n, r, 0, a);
}

int main(void)
{
  int i,j,k,m;
  int p,q;
  j=prime_make(prms);
  for (i=0;i<j;i++){
      printf("%d ", prms[i]);
  }
  int st, ed, an;
  printf("\n");
  while(1){
      printf("input [MIN] [MAX] [TTL]\n");
      scanf("%d%d%d", &st, &ed, &an );
      printf("input no %d %d %d\n", st, ed, an);
      p=q=-1;
      for (i=0;i<j;i++){
          if(prms[i]==st) p=i;
          if(prms[i]==ed) q=i;
      }
      if (p==-1 || q==-1) break;
      printf("select no %d %d %d\n", prms[p], prms[q], an);
      for (m=2;m<q-p;m++)
          combinations(p,q,an,m);
    }
  return 0;
}

Comments

[kuma_dansyaku]

回答ありがとうございます。
ソースコードまで添付して頂き本当にありがとうございます。
とても参考になりました。

Answer 4

レスをくれた皆さん、丁寧に回答して頂き本当にありがとうございました。

頂いた回答の中にこの問題は幅優先探索 or 深さ優先探索を勉強すると良いと教えていただいたので調べてみました。
その上で解った事をここに書いてお礼に代えさせて頂きます。

幅優先探索 Wikipediaで見るとこんな感じ。
何故これで今回の問題が解決するのか解らない。

パターンを図に当てはめてみるとこんな感じかな。

![

取りあえず図解にすると何となく解る。
幅優先探索を探すとキューによる実装ばかりが見つかる。
深さ優先探索を探すとスタックを使った再帰ありと再帰なしの方法が見つかる。

この事から
幅優先探索⇒キューを使った手法
深さ優先探索⇒スタックを使った手法

深さ優先探索の計算量は幅優先探索より小さい( 最悪のケースでは同じ )

と言う認識を得た。

幅優先探索で実装してみると意外と簡単に出来た(ただキューのバッファサイズを検討する必要あり)

#include <stdio.h>

#define TRUE  (1)   /* 成功 */
#define FASLE (0)   /* 失敗 */

#define QUEUE_SIZE (33554432)     /* キューの最大数(2^25) *//* 最悪のケースのみ */

int _queue_data[QUEUE_SIZE];    /* キュー格納バッファ */
int _queue_head = 0;  /* キューの先頭位置 */
int _queue_num = 0;   /* キューの使用数 */

int enqueue(int enq_data) {
    if ((_queue_head + _queue_num) < QUEUE_SIZE) {
        _queue_data[(_queue_head + _queue_num) % QUEUE_SIZE] = enq_data;
        _queue_num++;
        return TRUE;
    }
    else {
        return FASLE;
    }
}

int dequeue(int *deq_data) {
    if (_queue_num) {
        *deq_data = _queue_data[_queue_head];
        _queue_num--;
        _queue_head = (_queue_head + 1) % QUEUE_SIZE;
        return TRUE;
    }
    else {
        return FASLE;
    }
}


#define N (25)
int prime[N] = { 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 };  /* 1-100 までの素数たち */

int main() {
    int i, n, match_cnt;
    int imin, imax, ival, sum;

    printf("input [MIN] [MAX] [TTL]\n");
    scanf_s("%d%d%d", &imin, &imax, &ival);
    printf("input no %d %d %d\n", imin, imax, ival);

    for (i = 0; imin > prime[i]; i++);
    enqueue(0);             // 加算しない値
    enqueue(prime[i++]);    // 加算した値
    n = _queue_num;
    match_cnt = 0;

    while (_queue_num && prime[i] <= imax && i<N) {    // キューが空っぽになるか参照素数がimaxを越えるか素数要素を越えるまで繰り返す
        dequeue(&sum);
        n--;

        if (sum == ival || (sum + prime[i]) == ival) {
            match_cnt++;   // 一致した値
            continue;
        }
        if (sum < ival)                 enqueue(sum);               // 素数を加算しない値
        if ((sum + prime[i]) < ival)    enqueue(sum + prime[i]);    // 素数を加算した値
        if (n == 0) {
            i++;
            n = _queue_num;
        }
    }
    printf("match=%d\n", match_cnt);

    return 0;
}

深さ優先探索は以下の通り(まずは再帰を使わない方法で基礎を理解しようと思います)

#include <stdio.h>

#define TRUE  (1)   /* 成功 */
#define FASLE (0)   /* 失敗 */

#define STACK_SIZE (1000)     /* スタックの最大数 *//* 最悪のケースっていくつなんだろう？ */

int _stack_data[STACK_SIZE];    /* スタック格納バッファ */
int _stack_num = 0;   /* スタックの使用数 */

int push(int stack_data) {
    /* TBD */
    return TRUE;
}

int pop(int *stack_data) {
    /* TBD */
    return TRUE;
}


#define N (25)
int prime[N] = { 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 };  /* 1-100 までの素数たち */

int main() {
    /* TBD */
    return 1;
}