1

基本的に、コードを実行するときに、大きな数を指定すると機能します（素数に分割しますが、小さな数で実行したい場合は機能しません）私が見る問題は、プログラム番号8を指定すると画面には何も表示されません (私は 2+2+2+2 と関係があると思います)。 50 と書くと、行に 1 つの素数を繰り返さずにすべての可能性が表示されます。

#include <math.h>
#include <stdio.h>
#include <stdlib.h>


#define is_sol  2
#define is_pos  4
#define impos  0

int n, *st;

int prim (int n)
{ 
    if ( n < 2 ) 
        return impos;
    else
        if ( n != 2 && (n % 2) == 0)
            return impos;
        else 
        { long i;
    for(i = 3; i <=sqrt(1.0*n); i +=2)
        if ( n % i == 0)
            return impos;
    }
    return is_pos;                   
}

int test(int h)
{  
    int i;
    if(!h) 
        return (st[h] < 2 ? impos : prim(st[h]));
    if(st[h] <= st[h-1]) 
        return impos;
    int p = st[h];
    if(!prim(p)) 
        return impos;
    int S = 0;
    for(i = 0 ; i <= h ; i++)
        S += st[i];
    if(S == n) 
        return is_sol;
    return (S < n ? is_pos : impos);
}

void print (int h)
{    
    int i;
    for(i = 0 ; i <= h; i++)
        printf("%d ", st[i]);
    printf("\n");
}

void back(int h) 
{ 
    int k;
    for(k = 2; k <= n/2; k++) 
    { 
        st[h] = k;
        int rez = test(h);
        if(rez == is_sol)
            print(h);
        else 
        { 
            if(rez == is_pos)
                back(h+1);
        }
    }
}

int main()
{ 
    printf( "Your number: ");
    scanf("%d",&n);
    st = (int*)malloc(sizeof(int)*(n/2));
    back(0);
}
4

1 に答える 1

1

条件

for(k = 2; k <= n/2; k++)

責任があります。異なる素数の和として数を書きたい場合、小さな数に対しては、多くの場合、より大きな素数を 1 つ含める唯一の方法があります。n/2たとえば、8 を異なる素数の和として書く唯一の方法は です8 = 3 + 5。

あなたがそれを作るならk <= n-2、それはうまくいくでしょう。

8 = 2+2+2+2またはのように、同じ素数を複数回使用できるようにする場合は、次の8 = 2+3+3ように変更する必要があります。

if(st[h] <= st[h-1])

に

if(st[h] < st[h-1])

でtest。

そして、最も露骨な非効率を避けるために、これまでの合計を追跡する必要があります。(そして、毎回各数値をチェックする代わりに、素数のリストを保存します。)

于 2013-01-30T22:01:51.640 に答える