모든 챌린지
쉬움 0명 해결 정답률 0%

쌍둥이 소수

한계값 이하의 쌍둥이 소수 쌍 (p, p + 2)를 모두 구합니다.

배우게 될 내용

  • 체로 한계값까지의 소수를 표시할 수 있습니다
  • 차이가 2인 소수를 찾아 훑을 수 있습니다
  • 쌍이 하나도 없을 만큼 작은 한계값을 처리할 수 있습니다

문제

원문 보기 (영어)

쌍둥이 소수는 11과 13, 17과 19처럼 차이가 2인 두 소수입니다. 큰 쪽이 limit 이하인 쌍을 모두 찾으세요.

twin_primes(limit) 함수를 구현하세요.

한계값이 클 때는 수를 하나씩 판별하지 말고 체를 이용해 소수를 한꺼번에 구하세요.

입력

limit: 쌍에서 큰 소수가 가질 수 있는 최댓값입니다.

출력

두 수가 모두 소수이고 p + 2 ≤ limit인 쌍 [p, p + 2]의 리스트를 p의 오름차순으로 정렬해 반환합니다. 쌍이 없으면 빈 리스트를 반환합니다.

제약 조건

0 ≤ limit ≤ 10^6

예시

예시 1
입력:
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]]입니다.

예시 2
입력:
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에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

아직 통과한 풀이가 없습니다. 풀어서 1위를 차지하세요.

다른 사람의 풀이 보기

커뮤니티 솔루션

아직 공개된 풀이가 없습니다. 문제를 풀고 첫 풀이를 공유하세요.