Некоторые квадратные трёхчлены хорошо порождают простые числа: n² + n + 41 даёт простые числа при всех n от 0 до 39. Для целых a и b, где |a| ≤ limit и |b| ≤ limit, посчитайте, при скольких подряд идущих значениях n = 0, 1, 2, ... число n² + an + b простое. Счёт останавливается на первом значении, которое не является простым. Найдите пару с самой длинной серией.
Реализуйте quadratic_primes(limit).
Входные данные
limit: ограничение на модули a и b.
Выходные данные
Верните [a, b, run], где run - количество простых чисел в самой длинной серии. Если таких пар несколько, возьмите пару с наименьшим a, а среди них с наименьшим b. Числа меньше 2 не простые, поэтому у пары, значение которой при n = 0 не простое, серия равна 0.
Ограничения
0 ≤ limit ≤ 300
Примеры
Ввод:
limit = 3
Ожидаемый вывод:
expected = [-2, 3, 3]
Ввод:
long long limit = 3;
Ожидаемый вывод:
std::vector<long long> expected = {-2, 3, 3};
Ввод:
long limit = 3;
Ожидаемый вывод:
long[] expected = new long[] {-2, 3, 3};
Пояснение
При a = −2 и b = 3 значения для n = 0, 1, 2, 3 равны 3, 2, 3, 6: три простых числа. Лучшей пары нет, и ни одна пара с меньшим a не даёт такой же серии, поэтому ответ [-2, 3, 3].
Ввод:
limit = 1
Ожидаемый вывод:
expected = [-1, -1, 0]
Ввод:
long long limit = 1;
Ожидаемый вывод:
std::vector<long long> expected = {-1, -1, 0};
Ввод:
long limit = 1;
Ожидаемый вывод:
long[] expected = new long[] {-1, -1, 0};
Пояснение
b равно −1, 0 или 1, и ни одно из этих чисел не простое, поэтому все серии равны 0 и побеждает наименьшая пара: [-1, -1, 0].
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
При n = 0 значение равно b, поэтому b должно быть простым, иначе серии нет вообще.
Подсказка 2
Увеличивайте n, пока значение остаётся простым; отрицательные значения и значения меньше 2 обрывают серию.
Подсказка 3
Перебирайте a и b по возрастанию и заменяйте лучший результат, только если серия строго длиннее.
Ожидаемая сложность
время O(limit² × run × √V), доп. память O(1)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.