E D R , A S I H C RSS

Carmichael Numbers

원문보기
----
인기도:B(A,B,C), 성공률:보통(낮음,보통,높음), 레벨:2(1~4)

About CarmichaelNumbers

암호 알고리즘 중에는 큰 소수를 활용하는 것도 있다. 하지만 어떤 큰 수가 소수인지를 판단하는 것은 그리 쉽지 않다.
페르마 테스트와 같이 빠른 속도로 매우 정확하게 소수 여부를 판단할 수 있는 확률적 소수 테스트 방법이라는 것이 있다. 소수 여부를 판단해야 할 정수 n이 주어졌을 때 a는 2이상 n-1이하의 난수라고 하자. 그러면 다음과 같은 식이 성립하면 n은 소수일 가능성이 있다.

a^n mod n = a

어떤 정수가 이러한 페르마 테스트를 여러 번 통과하면 그 정수는 소수일 가능성이 높다고 할 수 있다. 하지만 안 좋은 소식도 있다. 합성수(소수가 아닌 수) 중에는 그 수보다 작은 모든 정수에 대해 이 페르마 테스트를 통과하는 것도 있다. 이런 수를 카마이클 수라고 부른다.

주어진 정수가 카마이클 수인지 테스트하기 위한 프로그램을 만들어라.

Input

입력은 여러 줄로 구성되며 각 줄에는 작은 양의 정수 n(2

Output

입력된 각 수에 대해 아래에 있는 출력 예에 나와있는 식으로 그 수가 카마이클 수인지 아닌지를 판단한 결과를 출력하라.

Sample Input

~cpp 
1729
17
561
1109
431
0

Sample Output

~cpp 
The number 1729 is a Carmichael number.
17 is normal.
The number 561 is a Carmichael number.
1109 is normal.
431 is normal.

풀이

작성자 사용언어 개발시간 코드
문보창 C++ 3h 30m CarmichaelNumbers/문보창
조현태 C . CarmichaelNumbers/조현태

쓰레드

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2009-05-27 07:09:19
Processing time 0.2016 sec