Предположение о гипотезе Гольдбаха (с)

Question

Мой профессор попросил меня составить программу для проверки гипотезы Гольдбаха. Мне интересно, должен ли я считать 1 как простое число. Это мой код, который печатает первую комбинацию простых чисел:

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

int main()
{
    int n, i, j, k, l;    
    char prime, prime1;
    do   //check if n is even and greater than 2
    {
        printf("Give me an even natural number greater than 2:\n\n>");
        scanf("%d", &n);
    }
    while (n % 2 != 0 && n >= 2);
    for (i = 1; i < n ; i++) 
    {                   
        prime = 1;     
        for (k = 2; k < i; k++)  
            if (i % k == 0)
                prime = 0;
        if (prime)
        {
            for (j = 1; j < n; j++)
            {
                prime1 = 1;
                for (l = 2; l < j; l++)
                    if (j % l == 0)
                        prime1 = 0;
                if (prime1)
                    if (i + j == n)
                    {
                        printf("\n\n%d and %d are the first two prime numbers that add up to %d.\n", i, j, n);
                        return 0;
                    }
            }
        }
    }
}

Я проверил интернет, и почти все говорят, что 1 не простое число. Что я должен делать? Сохранить программу как есть или изменить так, чтобы она не рассматривалась как 1 как простое число? И как мне это сделать?:П

Answer 1

Вы можете рассмотреть 1 простое число, как это сделал Гольдбах, или нет, как это принято чаще, оно практически не имеет значения в отношении гипотезы.

принимая во внимание 1 как простое число имеет такой эффект:

• есть решение для 2: 1 + 1,
• первая пара для 4 является 1 + 3 вместо 2 + 2
• первое решение для более четных чисел может включать 1 если значение представляет собой простое число плюс один, но никакое известное четное число больше 2 не может быть выражено только как p + 1,

Обратите внимание, что в вашем коде есть проблемы:

• Вы не проверяете возвращаемое значение scanf()поэтому ввод строки, не являющейся числом, приведет к неопределенному поведению (в первый раз n неинициализирован) или бесконечный цикл как n больше не изменяется.

• тест while (n % 2 != 0 && n >= 2); неверно: должно быть:

  while (n <= 2 || n % 2 != 0);
  

• первый цикл может повторяться вдвое длиннее с тестом i <= n / 2

• второй цикл может пройти намного меньше с тестом k * k <= i

• вы можете выйти из второго цикла, когда вы обнаружите, что i не простое

• нет необходимости в третьем цикле, вам просто нужно проверить, n - i простое

• такие же улучшения возможны для второго основного теста, лучше перенести это в отдельную функцию.

• у вас должно быть сообщение и return утверждение для удаленной возможности найти контрпример к гипотезе Гольдбаха;-)

Вот улучшенная версия:

#include <stdio.h>

#define PRIME_MASK ((1ULL <<  2) | (1ULL <<  3) | (1ULL <<  5) | (1ULL <<  7) |\
                    (1ULL << 11) | (1ULL << 13) | (1ULL << 17) | (1ULL << 19) | \
                    (1ULL << 23) | (1ULL << 29) | (1ULL << 31) | (1ULL << 37) | \
                    (1ULL << 41) | (1ULL << 43) | (1ULL << 47) | (1ULL << 53) | \
                    (1ULL << 59) | (1ULL << 61))

int isprime(unsigned long long n) {
    if (n <= 63)
        return (PRIME_MASK >> n) & 1;
    if (n % 2 == 0)
        return 0;
    for (unsigned long long k = 3; k * k <= n; k += 2) {
        if (n % k == 0)
            return 0;
    }
    return 1;
}

int main(void) {
    unsigned long long n, i;
    int r;

    for (;;) {
        printf("Give me an even natural number greater than 2:\n>");
        r = scanf("%llu", &n);
        if (r == 1) {
            if (n % 2 == 0 && n > 2)
                break;
        } else
        if (r == EOF) {  /* premature end of file */
            return 1;
        } else {
            scanf("%*[^\n]%*c");  /* flush pending line */
        }
    }
#ifdef ONE_IS_PRIME
    i = 1;    /* start this loop at 1 if you want to assume 1 is prime */
#else
    i = (n == 4) ? 2 : 3;
#endif
    for (; i <= n / 2; i += 2) {
        if (isprime(i) && isprime(n - i)) {
            printf("%llu = %llu + %llu\n", n, i, n - i);
            return 0;
        }
    }
    printf("Goldbach was wrong!\n"
           " %llu cannot be written as the sum of two primes\n", n);
    return 0;
}

Answer 2

ВЫ МОЖЕТЕ Рассмотреть 1 как простое число, поскольку Гольдбах тоже считал его главным в своем письме Леонхарду Эйлеру. Но это было время, когда 1 считалось простым. Позднее оно было заброшено, и, следовательно, это третье пересмотренное предположение Гольдбаха. Кроме того, поскольку сегодня мы считаем, что 1 не является ни простым, ни составным, даже если вы не считаете 1 простым числом, гипотеза все еще остается верной, она хорошо проверена до 4*10^18 (повторно проверена до 4*10^17).

Если вы имеете дело с профессором, вам лучше спросить его, чего он хочет.