보통 0명 해결 정답률 0%

순환 소수

한계값 이하의 소수 중 자릿수를 어떻게 회전해도 소수인 수를 셉니다.

배우게 될 내용

  • 수의 자릿수를 회전할 수 있다
  • 모든 회전에 대해 조건을 확인할 수 있다
  • 조건을 통과한 수를 셀 수 있다

문제

원문 보기 (영어)

수를 회전한다는 것은 맨 앞 자리 숫자를 맨 뒤로 옮기는 것입니다. 197은 971이 되고, 다시 719가 됩니다. 모든 회전이 소수인 소수를 순환 소수라고 하며, 197은 순환 소수입니다. 2부터 limit까지의 순환 소수의 개수를 세세요. 회전한 수가 한계값보다 클 수도 있는데, 그래도 소수여야 합니다.

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

입력

limit: 확인할 가장 큰 수입니다.

출력

p ≤ limit인 소수 중 순환 소수의 개수를 반환합니다.

제약 조건

1 ≤ limit ≤ 100,000

예시

예시 1
입력:
limit = 20

예상 출력:
expected = 7
입력:
long long limit = 20;

예상 출력:
long long expected = 7;
입력:
long limit = 20;

예상 출력:
long expected = 7;

설명

2, 3, 5, 7, 11, 13(31이 소수), 17(71이 소수)은 순환 소수이지만 19는 아닙니다(91 = 7 × 13). 답은 7입니다.

예시 2
입력:
limit = 1

예상 출력:
expected = 0
입력:
long long limit = 1;

예상 출력:
long long expected = 0;
입력:
long limit = 1;

예상 출력:
long expected = 0;

설명

1 이하에는 소수가 없으므로 답은 0입니다.

접근 방법

먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.

힌트 1

한 번 회전하면 맨 앞 숫자가 맨 뒤로 갑니다. d자리 수에는 회전이 d개 있습니다.

힌트 2

수를 문자열로 바꾸면 회전하기 쉽습니다.

힌트 3

회전한 수는 한계값보다 클 수 있으므로 소수인지 직접 검사하세요.

예상 복잡도

시간 O(limit × d × √(10^d)) (나눗셈 시도법 사용 시), 추가 공간 O(d)

참고 자료

이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

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

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

다른 사람의 풀이 보기

커뮤니티 솔루션

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