c言語のコードに一部誤りがあるようですがそれがどこなのかわかりません

Question

ある自然数ｎを素数の足し算に分割し、その組み合わせの数を求めるプログラム（例えば5なら5、2+3。8なら、2+2+2+2、2+3+3、3+5といったような分け方。ｎ=0なら1が結果として出てきます）が一部の値に対してまちがった値を出すようなのですが、それが何故なのかわかりません。

コード#include <stdio.h>

int is_prime(n){
  int d = 2;
  int r = 1;
  int a ;
  while(r != 0 ){
    r = n % d;
    d = d + 1;
  }
     if(d == n + 1){
       a = 1;
       }else{a = 0;
       }
       return a;
}

 int division_into_primes(int n , int u){
   int a = 0;
   int p = u;
   if( n < u && n!=0){
     a = 0;
   }
     else if( n == 0){
       a = 1;
     }
        else{
          for( p = u ; p <= n ; p++){
            a = a + is_prime(p) * division_into_primes( n - p , p );
          }
        }
        return a;
     }
     
          
          
          
   main(){
     int n;
     int u = 2;
     scanf("%d",&n);
     printf("%d",division_into_primes( n , u));
}

Comments

[takotakot]

「一部の値」が具体的に分かると、解答の助けになると思います。

[退会済みユーザー]

すいません。それが、こちらもわからない状態なんです。
これは学校で出た課題で、機械採点されるのですが採点の結果が「ある値に対して間違った値を返す」だけだったので具体的にどの値なのかわからないのです。

[Stripe]

ところで、n=0のときに1になるというのは、あっているんですよね？（そのように出題されているんですよね？）。問題の主旨からすると、n=0もn=1も答えが0になりそうですが？

[退会済みユーザー]

はい。

Answer 1

まず、
is_prime()のパラメータの型が不明。・・・デフォルトでintになりますが
main()に型(int)とreturnがない。
・・・コンパイラでエラーなりワーニングなり出ませんでしたか？
で、

一部の値

っていくつですか？

Comments

[takotakot]

『すいません。それが、こちらもわからない状態なんです。 これは学校で出た課題で、機械採点されるのですが採点の結果が「ある値に対して間違った値を返す」だけだったので具体的にどの値なのかわからないのです。』と伺っております。

Answer 2

... ｎ=0なら1 ..

これは正しいのでしょうか？
n=0 なら 0 通りなのでは?

プログラムを少し変えてみました。
n = 0 以外ときの結果は同じです。
コンパイル時の 警告がでなくなるようにしたのと、
計算量をすこしすくなくてすむようにしました。

n = 100 の解を求めてみると、速度差がよくわかるとおもいます。

1部の値に対してまちがった値を出す

これについては私もわかりません。問題の意味をとりちがえていて、採点側と一致していない？

#include <stdio.h>

int is_prime(int n) {
  if (n < 2) {
    return 0;
  }
  // 2 .. n までの割り算を行い、約数を見つける。
  // みつけた約数が n 自身だったら n は素数と判断する。
  int d = 2;
  while (n % d != 0) {
    d += 1;
  }
  return (d == n);
}

int division_into_primes(int n, int min_v) {
  if (n < 1 || n < min_v) {
    return 0;
  }

  int a = 0;
  // n が素数なら それ自身で 1 つの解になる。
  // 次に 2 個以上の素数の和の解の数を求める。(再帰的に)
  if (is_prime(n) == 1) {
    a += 1;
  }
  for (int p = min_v; p < n; p++) {
    if (is_prime(p) == 1) {
      // p + ... の 形の解の数を求める。
      a += division_into_primes(n - p, p);
    }
  }
  return a;
}

int main() {
  for (int i = -1; i < 100; i++) {
    printf("%d -> %d\n", i, division_into_primes(i, 2));
  }
  return 0;
}
/**
-1 -> 0
0 -> 0
1 -> 0
2 -> 1
3 -> 1
4 -> 1
5 -> 2
6 -> 2
7 -> 3
8 -> 3
9 -> 4
**/

Answer 3

アルゴリズムの正否に関わらず、
INT_MAXを超えた値を入力した場合は間違った結果になります。
コンパイラ依存でint型のサイズが変わりますが、
4byteなら2147483647が入力可能な最大値となります。

Answer 4

パッと見た感じだと、division_into_primesの再起呼び出しの必要性が分かりませんでした。
for文の中の再起をやめて、以下のようにするのはどうでしょうか。

#include <stdio.h>

int is_prime(n){
  int d = 2;
  int r = 1;
  int a ;
  while(r != 0 ){
    r = n % d;
    d = d + 1;
  }
  if(d == n + 1){
    a = 1;
  }else{a = 0;
  }
  return a;
}

int division_into_primes(int n , int u){
  int a = 0;
  int p = u;
  if( n < u && n!=0){
    a = 0;
  }
  else if( n == 0){
    a = 1;
  }
  else{
    for( p = u ; p <= n ; p++){
//      a = a + is_prime(p) * division_into_primes( n - p , p );
      if(is_prime(p)==1){
	if(n%p==0){
	  a++;
	  if(n==p)
	    break;
	  n=n/p;
	  p=u-1;
	}
      }
    }
  }
  return a;
}
     
          
          
          
main(){
  int n;
  int u = 2;
  scanf("%d",&n);
  printf("%d",division_into_primes( n , u));
}

Answer 5

結果だけ見れば特に問題はないようですね？
~/test cat tst7.c

#include <stdio.h>

int is_prime(int n)
{
        int             d = 2;
        int             r = 1;
        int             a;
        while (r != 0) {
                r = n % d;
                d = d + 1;
        }
        if (d == n + 1) {
                a = 1;
        } else {
                a = 0;
        }
        return a;
}

int main()
{
    int cnt= 0;
    for (int i = 2; i < 1000; i++) {
        if (is_prime(i)) {
            cnt++;
            if((cnt & 0x0f)== 0){
                printf("%3d\n", i);
            }else{
                printf("%3d ", i);
            }
        }
    }
    printf("\ncount:%d\n", cnt);

    return 0;
}

~/test ./a.out
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 101 103 107 109 113 127 131
137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223
227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311
313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409
419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503
509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613
617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719
727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827
829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941
947 953 967 971 977 983 991 997
count:168
・・・素数の中身までは確認してないですが。

Answer 6

まず、is_prime 関数が「正しい」かどうか、チェックしましょう。
for ループを用いて、0 から 100 くらいまでの値について、処理させ、printf を使って、引数と、is_prime(n) の値を比べてみて下さい。

cateye 様によって、is_prime 関数は「正しい」と言えそうです。Stripe 様の回答と関連しますが、
n=1 はどういう解になるべきで、それは正しいのでしょうか。

Answer 7

ふむふむ、のっけから違う気がしますが・・・。
パターンを出力するならprintf("%d",division_into_primes( n , u));が１回てのがまず変ですね。

Comments

[cateye]

“組み合わせの数”と言ってるので、いくつ組み合わせがあるかが出力されるという事ではないでしょうか？
~/test ./a.out
5
2

[MasaakiIrie]

なるほど、そっちの意味でしたか！