About CarmichaelNumbers ¶
์ํธ ์๊ณ ๋ฆฌ์ฆ ์ค์๋ ํฐ ์์๋ฅผ ํ์ฉํ๋ ๊ฒ๋ ์๋ค. ํ์ง๋ง ์ด๋ค ํฐ ์๊ฐ ์์์ธ์ง๋ฅผ ํ๋จํ๋ ๊ฒ์ ๊ทธ๋ฆฌ ์ฝ์ง ์๋ค.
ํ๋ฅด๋ง ํ ์คํธ์ ๊ฐ์ด ๋น ๋ฅธ ์๋๋ก ๋งค์ฐ ์ ํํ๊ฒ ์์ ์ฌ๋ถ๋ฅผ ํ๋จํ ์ ์๋ ํ๋ฅ ์ ์์ ํ ์คํธ ๋ฐฉ๋ฒ์ด๋ผ๋ ๊ฒ์ด ์๋ค. ์์ ์ฌ๋ถ๋ฅผ ํ๋จํด์ผ ํ ์ ์ n์ด ์ฃผ์ด์ก์ ๋ a๋ 2์ด์ n-1์ดํ์ ๋์๋ผ๊ณ ํ์. ๊ทธ๋ฌ๋ฉด ๋ค์๊ณผ ๊ฐ์ ์์ด ์ฑ๋ฆฝํ๋ฉด n์ ์์์ผ ๊ฐ๋ฅ์ฑ์ด ์๋ค.
a^n mod n = a
์ด๋ค ์ ์๊ฐ ์ด๋ฌํ ํ๋ฅด๋ง ํ
์คํธ๋ฅผ ์ฌ๋ฌ ๋ฒ ํต๊ณผํ๋ฉด ๊ทธ ์ ์๋ ์์์ผ ๊ฐ๋ฅ์ฑ์ด ๋๋ค๊ณ ํ ์ ์๋ค. ํ์ง๋ง ์ ์ข์ ์์๋ ์๋ค. ํฉ์ฑ์(์์๊ฐ ์๋ ์) ์ค์๋ ๊ทธ ์๋ณด๋ค ์์ ๋ชจ๋ ์ ์์ ๋ํด ์ด ํ๋ฅด๋ง ํ
์คํธ๋ฅผ ํต๊ณผํ๋ ๊ฒ๋ ์๋ค. ์ด๋ฐ ์๋ฅผ ์นด๋ง์ดํด ์๋ผ๊ณ ๋ถ๋ฅธ๋ค.
์ฃผ์ด์ง ์ ์๊ฐ ์นด๋ง์ดํด ์์ธ์ง ํ
์คํธํ๊ธฐ ์ํ ํ๋ก๊ทธ๋จ์ ๋ง๋ค์ด๋ผ.
ํ๋ฅด๋ง ํ ์คํธ์ ๊ฐ์ด ๋น ๋ฅธ ์๋๋ก ๋งค์ฐ ์ ํํ๊ฒ ์์ ์ฌ๋ถ๋ฅผ ํ๋จํ ์ ์๋ ํ๋ฅ ์ ์์ ํ ์คํธ ๋ฐฉ๋ฒ์ด๋ผ๋ ๊ฒ์ด ์๋ค. ์์ ์ฌ๋ถ๋ฅผ ํ๋จํด์ผ ํ ์ ์ n์ด ์ฃผ์ด์ก์ ๋ a๋ 2์ด์ n-1์ดํ์ ๋์๋ผ๊ณ ํ์. ๊ทธ๋ฌ๋ฉด ๋ค์๊ณผ ๊ฐ์ ์์ด ์ฑ๋ฆฝํ๋ฉด n์ ์์์ผ ๊ฐ๋ฅ์ฑ์ด ์๋ค.
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/์กฐํํ |