문제
쌍둥이 소수는 11과 13, 17과 19처럼 차이가 2인 두 소수입니다. 큰 쪽이 limit 이하인 쌍을 모두 찾으세요.
twin_primes(limit) 함수를 구현하세요.
한계값이 클 때는 수를 하나씩 판별하지 말고 체를 이용해 소수를 한꺼번에 구하세요.
입력
limit: 쌍에서 큰 소수가 가질 수 있는 최댓값입니다.
출력
두 수가 모두 소수이고 p + 2 ≤ limit인 쌍 [p, p + 2]의 리스트를 p의 오름차순으로 정렬해 반환합니다. 쌍이 없으면 빈 리스트를 반환합니다.
제약 조건
0 ≤ limit ≤ 10^6
예시
입력:
limit = 20
예상 출력:
expected = [
[3, 5],
[5, 7],
[11, 13],
[17, 19]
]
입력:
long long limit = 20;
예상 출력:
std::vector<std::vector<long long>> expected = {
{3, 5},
{5, 7},
{11, 13},
{17, 19}
};
입력:
long limit = 20;
예상 출력:
long[][] expected = new long[][] {
new long[] {3, 5},
new long[] {5, 7},
new long[] {11, 13},
new long[] {17, 19}
};
설명
20 이하의 소수는 2, 3, 5, 7, 11, 13, 17, 19이고, 그중 차이가 2인 쌍은 [[3, 5], [5, 7], [11, 13], [17, 19]]입니다.
입력:
limit = 6
예상 출력:
expected = [
[3, 5]
]
입력:
long long limit = 6;
예상 출력:
std::vector<std::vector<long long>> expected = {
{3, 5}
};
입력:
long limit = 6;
예상 출력:
long[][] expected = new long[][] {
new long[] {3, 5}
};
설명
3과 5는 모두 소수이고 5 ≤ 6이지만 7은 한계값을 넘으므로 [[3, 5]]뿐입니다.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
체를 쓰면 10^6까지의 소수를 수마다 판별하는 것보다 훨씬 빨리 구할 수 있습니다.
힌트 2
그다음 p + 2 ≤ limit인 모든 p를 확인하세요.
힌트 3
첫 번째 쌍이 (3, 5)이므로 한계값이 5보다 작으면 빈 리스트입니다.
예상 복잡도
시간 O(limit log log limit), 추가 공간 O(limit)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.