goldbach.c

   1 /*
   2  * Demonstrates Goldbach's conjecture (uses brute-force), more info at:
   3  *
   4  * http://en.wikipedia.org/wiki/Goldbach%27s_conjecture
   5  *
   6  * Luiz Fernando N. Capitulino
   7  * <lcapitulino@gmail.com>
   8  */
   9 #include <stdio.h>
  10 #include <stdlib.h>
  11
  12 #define SIZE 10
  13
  14 int is_prime(int num)
  15 {
  16         int i;
  17
  18         if (num < 2)
  19                 return 0;
  20
  21         for (i = 2; i < num; i++)
  22                 if (!(num % i))
  23                         return 0;
  24         return 1;
  25 }
  26
  27 int find_prime_sum(int num)
  28 {
  29         int i, j;
  30
  31         for (i = 2; i < num; i++)
  32                 if (is_prime(i)) {
  33                         if ((i + i) == num) {
  34                                 printf("%d + %d = %d\n", i, i, num);
  35                                 return 0;
  36                         }
  37                         for (j = i + 1; j + i <= num; j++)
  38                                 if (is_prime(j))
  39                                         if ((j + i) == num) {
  40                                                 printf("%d + %d = %d\n",
  41                                                        j, i, num);
  42                                                 return 0;
  43                                         }
  44                 }
  45         return 1;
  46 }
  47
  48 void golbach(const int *vet, int len)
  49 {
  50         int i, ret;
  51
  52         for (i = 0; i < len; i++) {
  53                 int num = vet[i];
  54
  55                 if (!(num % 2) && num > 2) {
  56                         ret = find_prime_sum(num);
  57                         if (ret) {
  58                                 fprintf(stderr, "failed for %d\n", num);
  59                                 exit(1);
  60                         }
  61                 }
  62         }
  63 }
  64
  65 int main(void)
  66 {
  67         int vet[SIZE], i;
  68
  69         for (i = 0; i < SIZE; i++) {
  70                 printf("next number [%d]: ", i + 1);
  71                 scanf("%d", &vet[i]);
  72         }
  73
  74         golbach(vet, SIZE);
  75         return 0;
  76 }