C++: гипотеза Гольдбаха

Бинарная проблема (гипотеза) Гольдбаха, она же проблема Эйлера, состоит в следующем:

Любое чётное число, начиная с 4, можно представить в виде суммы двух простых чисел.

Пока она проверена лишь для всех чётных чисел, не превышающих 1.2*1018. В общем виде не доказана.

Мы ставим перед собой более скромную задачу - проверить утверждение о том, что заданное чётное число n можно представить в виде суммы двух простых чисел.

Функции в коде служат следующей цели:

• int simple (unsigned long int n) - простая проверка числа n на простоту, вернёт 1 или 0;
• int goldbah1(unsigned long int n,unsigned long int &n1,unsigned long int &n2) - поиск "первой попавшейся" пары простых чисел n1, n2, составляющих в сумме чётное число n, n>3. Идея поиска такова: половину данного числа увеличивать до тех пор пока оно не станет простым, а второе находим вычитанием из n. Кажется, это работает :)
• int goldbah(unsigned long int n,unsigned long int &n1,unsigned long int &n2) - поиск и вывод в консоль всех пар простых слагаемых для заданного чётного n>3, тут просто перебор.

Вот вся программа, запускается goldbah, что изменить для запуска goldbah1 - написано //комментариями.

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

int simple (unsigned long int n) {
 unsigned long int i,l=floor(sqrt(n));
 if (n<2) return 0; //1 - не простое
 else if (n<4) return 1; //2,3 - простые
 else if (n%2==0) return 0; //четные - не простые
 for (i=3; i<=l; i+=2) if (n%i==0) return 0;
 return 1;
}

int goldbah(unsigned long int n,unsigned long int &n1,unsigned long int &n2) {
 unsigned long int halfn=n/2+1; int r=0;
 for (n1=2; n1<halfn; n1++)
 for (n2=n1; n2<n; n2++)
  if (n1+n2==n && simple(n1) && simple(n2)) {
   printf ("\n%lu=%lu+%lu",n,n1,n2);
   r++;
  }
 return r;
}

int goldbah1(unsigned long int n,unsigned long int &n1,unsigned long int &n2) {
 for (n1=n/2; n1<=n; n1++) if (simple(n1)) { n2=n-n1; return 1; }
 return 0;
}

int main () {
 unsigned long int n,n1,n2;
 printf ("\nВведите четное n>3: "); scanf ("%lu",&n);
 if (n<4 || n%2==1) {
  printf ("\nНеверный ввод, нажмите ENTER для выхода");
  fflush (stdin); getchar(); exit (1);
 }

 int found=goldbah(n,n1,n2); //Заменить goldbah на goldbah1
 if (!found) printf ("\nОтвет не найден");
// else printf ("\n%lu=%lu+%lu",n,n1,n2); //Раскомментарить строку

 printf ("\nНажмите ENTER для выхода");
 fflush (stdin); getchar(); return 0;
}

14.11.2013, 18:15 [13941 просмотр]