ํฌ ํ ํฉ ๊ฐ๊ฒ ๋ง๋ค๊ธฐ
-
ํ๋ก๊ทธ๋๋จธ์ค - ๋ ํ ํฉ ๊ฐ๊ฒ ๋ง๋ค๊ธฐAlgorithm 2022. 12. 9. 14:13
์๋ ๋ฌธ์ ๋ ํ๋ก๊ทธ๋๋จธ์ค์์ ์ ๊ณตํ๋ ๋ ํ ํฉ ๊ฐ๊ฒ ๋ง๋ค๊ธฐ์ ๋ฌธ์ ์ ๋๋ค๐ง๐ป๐ป ๋ฌธ์ ์ ์ ๋๋ณด๊ธฐ ์์ ์ ์ n์ด ์ฃผ์ด์ง๋๋ค. ์ด ์ซ์๋ฅผ k์ง์๋ก ๋ฐ๊ฟจ์ ๋, ๋ณํ๋ ์ ์์ ์๋ ์กฐ๊ฑด์ ๋ง๋ ์์(Prime number)๊ฐ ๋ช ๊ฐ์ธ์ง ์์๋ณด๋ ค ํฉ๋๋ค. 0P0์ฒ๋ผ ์์ ์์ชฝ์ 0์ด ์๋ ๊ฒฝ์ฐ P0์ฒ๋ผ ์์ ์ค๋ฅธ์ชฝ์๋ง 0์ด ์๊ณ ์ผ์ชฝ์๋ ์๋ฌด๊ฒ๋ ์๋ ๊ฒฝ์ฐ 0P์ฒ๋ผ ์์ ์ผ์ชฝ์๋ง 0์ด ์๊ณ ์ค๋ฅธ์ชฝ์๋ ์๋ฌด๊ฒ๋ ์๋ ๊ฒฝ์ฐ P์ฒ๋ผ ์์ ์์ชฝ์ ์๋ฌด๊ฒ๋ ์๋ ๊ฒฝ์ฐ ๋จ, P๋ ๊ฐ ์๋ฆฟ์์ 0์ ํฌํจํ์ง ์๋ ์์์ ๋๋ค. ์๋ฅผ ๋ค์ด, 101์ P๊ฐ ๋ ์ ์์ต๋๋ค. ์๋ฅผ ๋ค์ด, 437674์ 3์ง์๋ก ๋ฐ๊พธ๋ฉด 211020101011์ ๋๋ค. ์ฌ๊ธฐ์ ์ฐพ์ ์ ์๋ ์กฐ๊ฑด์ ๋ง๋ ์์๋ ์ผ์ชฝ๋ถํฐ ์์๋๋ก 211, 2, 11..