Carmichael Numbers

2020年1月17日 1068点热度 0人点赞 0条评论

Carmichael Numbers

时间: 1ms        内存:64M

描述:

Certain cryptographic algorithms make use of big prime numbers. However, checking whether a big number is prime is not so easy. Randomized primality tests exist that offer a high degree of confidence of accurate determination at low cost, such as the Fermat test. Let a be a random number between 2 and n - 1, where n is the number whose primality we are testing. Then, n is probably prime if the following equation holds: an mod n = a If a number passes the Fermat test several times, then it is prime with a high probability. Unfortunately, there is bad news. Certain composite numbers (non-primes) still pass the Fermat test with every number smaller than themselves. These numbers are called Carmichael numbers. Write a program to test whether a given integer is a Carmichael number.

输入:

The input will consist of a series of lines, each containing a small positive number n ( 2 < n < 65, 000). A number n = 0 will mark the end of the input, and must not be processed.

输出:

For each number in the input, print whether it is a Carmichael number or not as shown in the sample output

示例输入:

1729
17
561
1109
431
0

示例输出:

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

提示:

参考答案:

解锁文章

没有看到答案?微信扫描二维码可免费解锁文章

微信扫描二维码解锁

使用微信扫描二维码打开广告页面后可以立即关闭,再刷新此页面即可正常浏览此文章

所跳转广告均由第三方提供,并不代表本站观点!

已经扫描此二维码?点此立即跳转

code

这个人很懒,什么都没留下

文章评论