imported>Unknown at 05:22, 7 February 2021

2021-02-07T05:22:49Z

New page

[http://acm.uva.es/p/v100/10006.html 원문보기]
----
인기도:B(A,B,C), 성공률:보통(낮음,보통,높음), 레벨:2(1~4)

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

a^n mod n = a

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

주어진 정수가 카마이클 수인지 테스트하기 위한 프로그램을 만들어라.
=== Input ===
입력은 여러 줄로 구성되며 각 줄에는 작은 양의 정수 n(2<n<65,000)이 입력된다. n=0은 입력의 끝을 나타내며, 그 줄은 처리하지 않는다.
=== Output ===
입력된 각 수에 대해 아래에 있는 출력 예에 나와있는 식으로 그 수가 카마이클 수인지 아닌지를 판단한 결과를 출력하라.
=== Sample Input ===
1729
17
561
1109
431
0

=== Sample Output ===
The number 1729 is a Carmichael number.
17 is normal.
The number 561 is a Carmichael number.
1109 is normal.
431 is normal.

=== 풀이 ===
{| class="wikitable"
|-
| 작성자
| 사용언어
| 개발시간
| 코드
|-
| [[문보창]]
| C++
| 3h 30m
| [[CarmichaelNumbers/문보창]]
|-
| [[조현태]]
| C
| .
| [[CarmichaelNumbers/조현태]]
|}

=== 쓰레드 ===
----
[[문제분류]] [[AOI]]

CarmichaelNumbers - Revision history

imported>Unknown at 05:22, 7 February 2021