goldbach.c

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