반응형
Baekjoon Online Judge의 13319번 가짜 소수 문제의 Text풀이입니다.
13319번: 가짜 소수
지구이는 우연히 오일러 프로젝트에서 100억 정도의 매우 큰 숫자가 소수인지 판별해야만 풀리는 문제를 보게 되었다. 지구이는 2부터 sqrt(N) 까지 모든 숫자로 나누는 방법으로 코딩했지만, 1시
www.acmicpc.net
💻코드
##🧠풀이
페르마의 소정리와 카마이클 수를 이용한 문제이다.
https://en.wikipedia.org/wiki/Carmichael_number
Carmichael number - Wikipedia
From Wikipedia, the free encyclopedia Composite number in number theory In number theory, a Carmichael number is a composite number n {\displaystyle n} , which in modular arithmetic satisfies the congruence relation: b n ≡ b ( mod n ) {\displaystyle b^{n
en.wikipedia.org
🤔느낀 점
문제 조건을 대충 읽어 조금 헤맸다...
반응형
댓글