2

Задача - посчитать количество представлений числа в виде суммы двух простых (задача на гипотезу гольдбаха). Например, пусть f(x) и есть функция которая выдает количество таких представлений:

f(10) = 2:
10 = 5 + 5 = 3 + 7

f(14) = 2:
14 = 3 + 11 = 7 + 7

f(6) = 1:
6 = 3 + 3

f(11) = 0

Вот код решения:

#include <bits/stdc++.h>
#define optimize(); std::ios_base::sync_with_stdio(0); std::cin.tie(0);
using namespace std;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef long long ll;
 
bool check_prime(ui n)
{
    for (size_t i = 2; i*i <= n; i++)
    {
        if (n % i == 0)
            return false;
    }
    return true;
}
 
int main()
{
    optimize(); //не влияет на решение
    int n;
    cin >> n;
    if (n % 2) //нечетные числа нельзя представить в виде суммы двух простых
        cout << 0;
    else //случай когда это сделать можно
    {
        ui cnt = 0;
        for (size_t i = 2; i <= n/2; i++)
            if (check_prime(i))
                if (check_prime(n - i))
                    cnt++;
        cout << cnt;
    }
}

Тесты с ACMP мне говорят, что на одном из тестов неверный ответ.

Числа принадлежат отрезку [4;10000] соответственно это точно не переполнение.

Асимптотика моего решения O(n^(3/2)). Так что в самый худший тест я должен буду сделать (10000sqrt(10000)) = 10^6 шагов (ну на самом деле 5*10^5, но это не важно), а в 1 секунду я точно должен уложиться.

Значит, алгоритм поиска представления чисел скорее всего неверен? (хотя мне он кажется 100% верен)

Либо я какой-то частный случай упустил (хотя на деле их тут вроде и нет).

Что в моем коде не так?

4
  • 1
    У вас в optimize(); в обоих местах ; лишняя. В main она не нужна, потому что уже есть в конце макроса, а в самом #define - потому что она становится первым символом макроса. Commented 17 июн. 2020 в 22:15
  • @HolyBlackCat То есть #define распознает именно optimize() а потом ';std::ios_base::sync_with_stdio(0); std::cin.tie(0);'?
    – Learpcs
    Commented 17 июн. 2020 в 22:51
  • Угу, так и есть. Commented 17 июн. 2020 в 22:54
  • понял, спасибо за замечание!
    – Learpcs
    Commented 17 июн. 2020 в 22:54

1 ответ 1

6

На самом деле, у вас всё работает правильно, просто не понятно с чего вы взяли, что нечётные числа нельзя представить в виде суммы. Например число 7 представимо в виде 5+2. Так что просто убирайте строчку с проверкой на нечётность, и всё пройдёт) И еще, в дефайне допишите cout.tie:

#define optimize();   ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

Так что вот финальный код:

#include <bits/stdc++.h>
#define optimize(); std::ios_base::sync_with_stdio(0); std::cin.tie(0);
using namespace std;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef long long ll;
 
bool check_prime(ui n)
{
    for (size_t i = 2; i*i <= n; i++)
    {
        if (n % i == 0)
            return false;
    }
    return true;
}
 
int main()
{
    optimize(); //не влияет на решение
    int n;
    cin >> n;
 

        ui cnt = 0;
        for (size_t i = 2; i <= n/2; i++)
            if (check_prime(i))
                if (check_prime(n - i))
                    cnt++;
        cout << cnt;

}
4
  • ТОЧНО! Я просто рассуждал, что каждое простое число - нечетно. А насчет 2, как исключение, совершенно забыл.
    – Learpcs
    Commented 17 июн. 2020 в 21:51
  • 2
    Только не надо убирать проверку на нечетность. Для нечетных надо чисто проверить простоту n-2.
    – bipll
    Commented 18 июн. 2020 в 8:19
  • А зачем добавлять cout.tie(0)?
    – вася
    Commented 18 июн. 2020 в 11:39
  • не эффективная функция проверки числа на простоту Commented 18 июн. 2020 в 12:37

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.