Все задачи
Средне Решено: 0 Процент решений: 0%

Простые числа из квадратного трёхчлена

Найдите квадратный трёхчлен n² + an + b, который даёт самую длинную серию простых чисел, начиная с n = 0.

Чему вы научитесь

  • Проверять число на простоту перебором делителей
  • Перебирать пространство из двух параметров
  • Применять правила выбора при равенстве

Условие

Некоторые квадратные трёхчлены хорошо порождают простые числа: 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

Примеры

Пример 1
Ввод:
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].

Пример 2
Ввод:
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. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

Принятых решений пока нет. Решите задачу и займите первое место.

Учитесь у других

Решения сообщества

Пока нет опубликованных решений. Решите задание, чтобы поделиться первым.