Задача - посчитать количество представлений числа в виде суммы двух простых (задача на гипотезу гольдбаха). Например, пусть 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% верен)
Либо я какой-то частный случай упустил (хотя на деле их тут вроде и нет).
Что в моем коде не так?
optimize();
в обоих местах;
лишняя. Вmain
она не нужна, потому что уже есть в конце макроса, а в самом#define
- потому что она становится первым символом макроса.