整数的素数和分解

【问题描述】
歌德巴赫猜想说任何一个不小于6的偶数都可以分解为两个奇素数之和。对此问题扩展，如果一个整数能够表示成两个或多个素数之和，则得到一个素数和分解式。对于一个给定的整数，输出所有这种素数和分解式。注意，对于同构的分解只输出一次（比如5只有一个分解2 + 3，而3 + 2是2 + 3的同构分解式）。

例如，对于整数8，可以作为如下三种分解：
(1) 8 = 2 + 2 + 2 + 2
(2) 8 = 2 + 3 + 3
(3) 8 = 3 + 5

【算法分析】
由于要将指定整数N分解为素数之和，则首先需要计算出该整数N内的所有素数，然后递归求解所有素数和分解即可。

 

先是要求出N内的所有素数...再递归

void decompose(int num, int Primes[], int from, int Prime_counts)
{
  int i;
  if(num == 0)
   {
     print;
   }
  
  for(i=from; i<Prime_counts; ++i)
   {
     if(num < Primes[i])
       break;
       
     push_stack(S, Primes[i]);
     decompose( num-Primes[i] , Primes, i, Prime_counts);
     pop_stack(S);
   }
}

 

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

#define PRIMES_NUMS 8
#define QUIT 999

typedef struct stack
{
  int top;
  int* num;
}STACK;

STACK* S = NULL;

int is_prime(int num)
{
  int i;
  if(num%2==0)
    return 0;
  
  for(i=3; i<sqrt(num)+1; i+=2)
   {
     if(num%i == 0)
       return 0;
   }
   
   return 1;
}

int count_primes(int num, int Primes[])
{
  int i = 0;
  int count = 0;
  
  Primes[count++] = 2;
     
  for(i=3;i<num;i+=2)
   {
     if(is_prime(i))
       Primes[count++] = i;
   }
  
  return count;
}

void init_stack(STACK** S)
{
   *S = (STACK*)malloc(sizeof(STACK));
   (*S)->top = 0;
   (*S)->num = (int*)malloc(PRIMES_NUMS*sizeof(int));
}

void push_stack(STACK* S, int elements)
{
  S->num[S->top] = elements;
  S->top++;
}

int pop_stack(STACK* S)
{
  int element = S->num[S->top];
  S->top--;
  
  return element;
}

void decompose(int num, int Primes[], int from, int Prime_counts)
{
  int i;
  if(num == 0)
   {
     int j = 0;
     for(;j<S->top;j++)
       printf("%d\t",S->num[j]);
       
     printf("\n");
   }
  
  for(i=from; i<Prime_counts; ++i)
   {
     if(num < Primes[i])
       break;
       
     push_stack(S, Primes[i]);
     decompose( num-Primes[i] , Primes, i, Prime_counts);
     pop_stack(S);
   }
}

void print_primes(int Primes[], int Counts)
{
  int i;
  for(i=0;i<Counts;i++)
   printf("%d\t", Primes[i]);
   
  printf("\n");
}
     
int main(int argc, char *argv[])
{
  int number;
  int Primes[PRIMES_NUMS];
  int prime_count;
  
  init_stack(&S);
  printf("Please input the number you want to count:\n");
  scanf("%d",&number);
  
  while(number!=QUIT)
   {
     prime_count = count_primes(number, Primes);
     //print_primes(Primes, prime_count);

     decompose(number, Primes, 0, prime_count);
     printf("Please input the number you want to count:\n");
     scanf("%d",&number);
   }
   
  system("PAUSE");    
  return 0;
}