문제
소수를 잘 만들어 내는 이차식이 있습니다. n² + n + 41은 n = 0부터 39까지 모두 소수를 만듭니다. |a| ≤ limit, |b| ≤ limit인 정수 a, b에 대해 n = 0, 1, 2, ...를 차례로 넣었을 때 n² + an + b가 연속으로 몇 번 소수가 되는지 세세요. 처음으로 소수가 아닌 값이 나오면 멈춥니다. 연속 길이가 가장 긴 쌍을 찾으세요.
quadratic_primes(limit) 함수를 구현하세요.
입력
limit: a와 b의 절댓값의 상한입니다.
출력
[a, b, run]을 반환합니다. run은 가장 긴 연속 구간에 있는 소수의 개수입니다. 여러 쌍이 같으면 a가 가장 작은 것, 그다음 b가 가장 작은 것을 고릅니다. 2보다 작은 수는 소수가 아니므로, n = 0일 때의 값이 소수가 아닌 쌍의 run은 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 중 하나이고 모두 소수가 아니므로 모든 run이 0이며, 가장 작은 쌍이 선택되어 [-1, -1, 0]입니다.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
n = 0일 때 값은 b이므로, 연속 구간이 생기려면 b가 소수여야 합니다.
힌트 2
값이 소수가 아닐 때까지 n을 늘려 가며 세세요. 음수나 2보다 작은 값이 나오면 연속이 끝납니다.
힌트 3
a와 b를 오름차순으로 반복하고, 연속 길이가 엄격하게 더 길 때만 최선의 쌍을 바꾸세요.
예상 복잡도
시간 O(limit² × run × √V), 추가 공간 O(1)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.