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++)

负责。如果您想将一个数字写为不同素数之和，对于小数，唯一的方法通常包括一个大于的素数n/2- 例如，将 8 写为不同素数之和的唯一方法是8 = 3 + 5。

如果你做到了k <= n-2，它会起作用的。

如果您想允许多次使用相同的素数，例如8 = 2+2+2+2or 8 = 2+3+3，您需要更改

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

到

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

在test.

而且您应该跟踪到目前为止的总和，以避免最明显的低效率。（并存储一个素数列表，而不是每次都检查每个数字。）

于 2013-01-30T22:01:51.640 回答