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;
}

P.S. В реальности следует иметь в виду более эффективные (но требующие дополнительной памяти) алгоритмы вычисления простых чисел, такие как решето Эратосфена. Вот более современная версия той же программы, которая выполнялась в консоли Visual Studio 2019.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <numeric>
#include <clocale>
#include <windows.h>
using namespace std;

vector <unsigned long long int> v; //таблица простых чисел

void sieve(unsigned long long int n) { //поиск таблицы
 v.resize(n+1);
 iota(v.begin(),v.begin()+n+1,0);
 v[1] = 0; //1 - не простое
 for (unsigned long long int i = 2; i <= n; i++) {
  for (unsigned long long int j = i + 1; j <= n; j++) {
   if (v[j] == 0) continue;
   if (j % i == 0) {
    v[j] = 0;
    continue;
   }
  }
  if (i * i > n) break;
 }
}

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 && v[n1]!=0 && v[n2]!=0) {
    cout << "\n" << 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 (v[n1]!=0) { n2 = n - n1; return 1; }
 return 0;
}

int main() {
 setlocale(LC_ALL,".1251");
 SetConsoleCP(1251); SetConsoleOutputCP(1251);

 unsigned long int n, n1, n2;
 cout << "\nВведите четное n>3: ";
 cin >> n;
 if (!cin.good() || n < 4 || n % 2 == 1) {
  cout << "\nНеверный ввод";
  exit(1);
 }

 cout << "\nСоздаём таблицу...";
 sieve(n);

 cout << "\ngoldbah";
 int found = goldbah(n, n1, n2);
 if (!found) cout << "\nОтвет не найден";

 cout << "\ngoldbah1";
 int found2 = goldbah1(n, n1, n2);
 if (!found2) cout << "\nОтвет не найден";
 else cout << "\n" << n << "=" << n1 << "+" << n2;

 return 0;
}

Первое нечётное число, которое не раскладывается на сумму двух простых, равно 27:

27

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