\n\uc18c\uac1c<\/h2>\n
\uc54c\uace0\ub9ac\uc998 \ubb38\uc81c \ud574\uacb0\uc740 \ud504\ub85c\uadf8\ub798\ubc0d\uc758 \uae30\ubcf8\uc774\uba70, \ucf54\ub529 \uba74\uc811\uc5d0\uc11c\ub3c4 \uc911\uc694\ud55c \uc5ed\ud560\uc744 \ud569\ub2c8\ub2e4. \ubcf8 \uac15\uc88c\uc5d0\uc11c\ub294 \uc624\uc77c\ub7ec \ud53c \ud568\uc218(Euler’s Totient Function)\ub97c \uc2a4\uc704\ud504\ud2b8\ub85c \uad6c\ud604\ud574\ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uc624\uc77c\ub7ec \ud53c \ud568\uc218\ub294 \uc8fc\uc5b4\uc9c4 \uc591\uc758 \uc815\uc218 n\uc5d0 \ub300\ud574 n\uacfc \uc11c\ub85c\uc18c\uc778 \uc815\uc218\uc758 \uac1c\uc218\ub97c \ubc18\ud658\ud569\ub2c8\ub2e4. \uc989, 1\ubd80\ud130 n\uae4c\uc9c0\uc758 \uc815\uc218 \uc911\uc5d0\uc11c n\uacfc \ucd5c\ub300\uacf5\uc57d\uc218\uac00 1\uc778 \uc815\uc218\ub97c \uc138\ub294 \ud568\uc218\uc785\ub2c8\ub2e4.<\/p>\n<\/section>\n\n\uc54c\uace0\ub9ac\uc998 \ubb38\uc81c \uc124\uba85<\/h2>\n
\ubb38\uc81c:<\/strong> \uc815\uc218 n(1 \u2264 n \u2264 106<\/sup>)\uc774 \uc8fc\uc5b4\uc9c8 \ub54c, \uc624\uc77c\ub7ec \ud53c \ud568\uc218\ub97c \uacc4\uc0b0\ud558\uc5ec \ubc18\ud658\ud558\uc2dc\uc624.<\/p>\n\uc608\ub97c \ub4e4\uc5b4, n\uc774 6\uc77c \uacbd\uc6b0, 1, 2, 3, 4, 5, 6 \uc911\uc5d0\uc11c 1\uacfc \uc11c\ub85c\uc18c\uc778 \uc218\ub294 1, 5\uc774\uba70, 2\uc640 \uc11c\ub85c\uc18c\uc778 \uc218\ub294 1, 3, 5\uc774\ubbc0\ub85c \ucd5c\uc885\uc801\uc73c\ub85c 2\uac00 \ub429\ub2c8\ub2e4. \ub530\ub77c\uc11c \u03c6(6) = 2\uc785\ub2c8\ub2e4.<\/p>\n<\/section>\n\n\ubb38\uc81c \uc811\uadfc \ubc29\ubc95<\/h2>\n
\uc624\uc77c\ub7ec \ud53c \ud568\uc218\ub294 \uc8fc\uc5b4\uc9c4 \uc218\uc758 \uc18c\uc778\uc218\ub97c \ud65c\uc6a9\ud558\uc5ec \ud6a8\uc728\uc801\uc73c\ub85c \uacc4\uc0b0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc774 \ud568\uc218\ub294 \ub2e4\uc74c\uc758 \uc131\uc9c8\uc744 \ud1b5\ud574 \uad6c\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4:<\/p>\n
\n- \u03c6(p) = p – 1 (p\ub294 \uc18c\uc218)<\/li>\n
- \u03c6(pk<\/sup>) = pk<\/sup> – pk-1<\/sup> (p\ub294 \uc18c\uc218, k\ub294 \uc591\uc758 \uc815\uc218)<\/li>\n
- \u03c6(mn) = \u03c6(m) * \u03c6(n) (m\uacfc n\uc740 \uc11c\ub85c\uc18c)<\/li>\n<\/ul>\n
\ub530\ub77c\uc11c, \uc624\uc77c\ub7ec \ud53c \ud568\uc218\ub294 \uc18c\uc778\uc218 \ubd84\ud574\ub97c \ud1b5\ud574 \uacc4\uc0b0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574 \ub2e4\uc74c\uacfc \uac19\uc740 \ub2e8\uacc4\ub85c \uc9c4\ud589\ud560 \uac83\uc785\ub2c8\ub2e4:<\/p>\n
\n- \uc0ac\uc6a9\uc790\ub85c\ubd80\ud130 \uc815\uc218 n\uc744 \uc785\ub825\ubc1b\uc2b5\ub2c8\ub2e4.<\/li>\n
- n\uc758 \uc18c\uc778\uc218\ub97c \ucc3e\uace0, \uc774\ub97c \uc774\uc6a9\ud574 \uc624\uc77c\ub7ec \ud53c \ud568\uc218\ub97c \uacc4\uc0b0\ud569\ub2c8\ub2e4.<\/li>\n
- \uacc4\uc0b0 \uacb0\uacfc\ub97c \ucd9c\ub825\ud569\ub2c8\ub2e4.<\/li>\n<\/ol>\n<\/section>\n\n
\uc2a4\uc704\ud504\ud2b8 \ucf54\ub4dc \uad6c\ud604<\/h2>\n
\uc774\uc81c \uc2a4\uc704\ud504\ud2b8\ub97c \uc0ac\uc6a9\ud558\uc5ec \uc624\uc77c\ub7ec \ud53c \ud568\uc218\ub97c \uad6c\ud604\ud574\ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \ucf54\ub4dc\ub294 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4:<\/p>\n
\n
Euler’s Totient Function in Swift<\/h3>\n
\n func eulerTotient(n: Int) -> Int {
\n var result = n
\n var i = 2<\/p>\n while i * i <= n {
\n if n % i == 0 {
\n while n % i == 0 {
\n n \/= i
\n }
\n result -= result \/ i
\n }
\n i += 1
\n }<\/p>\n
if n > 1 {
\n result -= result \/ n
\n }<\/p>\n
return result
\n }<\/p>\n
\/\/ \uc608\uc2dc \uc0ac\uc6a9
\n let n = 6
\n print(\"\u03c6(\\(n)) = \\(eulerTotient(n: n))\") \/\/ Output: \u03c6(6) = 2
\n <\/code>\n<\/div>\n<\/section>\n\n\ucf54\ub4dc \uc124\uba85<\/h2>\n
\uc704 \ucf54\ub4dc\ub294 \uc624\uc77c\ub7ec \ud53c \ud568\uc218\ub97c \uacc4\uc0b0\ud558\ub294 \uba54\uc18c\ub4dc\ub97c \uc815\uc758\ud558\uace0 \uc788\uc2b5\ub2c8\ub2e4. \uac01 \ub2e8\uacc4\ub294 \ub2e4\uc74c\uacfc \uac19\uc774 \uc774\ub8e8\uc5b4\uc9d1\ub2c8\ub2e4:<\/p>\n
\n- \ucd08\uae30\ud654:<\/strong> \uc785\ub825\ubc1b\uc740 n \uac12\uc744 result\uc5d0 \uc800\uc7a5\ud569\ub2c8\ub2e4. result\ub294 \ucd5c\uc885 \uacb0\uacfc\ub97c \uc800\uc7a5\ud560 \ubcc0\uc218\uc785\ub2c8\ub2e4.<\/li>\n
- \uc18c\uc778\uc218 \ubd84\ud574:<\/strong> n\uc758 \uc18c\uc778\uc218\ub97c \ucc3e\uae30 \uc704\ud574 2\ubd80\ud130 \uc2dc\uc791\ud558\uc5ec i\ub97c \uc99d\uac00\uc2dc\ud0a4\uba70 \ubc18\ubcf5\ud569\ub2c8\ub2e4. i\uc758 \uc81c\uacf1\uc774 n\ubcf4\ub2e4 \uc791\uac70\ub098 \uac19\uc744 \ub54c\uae4c\uc9c0 \uc9c4\ud589\ud569\ub2c8\ub2e4.<\/li>\n
- \uc870\uac74 \ud655\uc778:<\/strong> n\uc774 i\ub85c \ub098\ub204\uc5b4 \ub5a8\uc5b4\uc9c0\uba74, while \ubb38\uc744 \ud1b5\ud574 n\uc744 i\ub85c \ub098\ub204\uc5b4\uc90d\ub2c8\ub2e4. \uc774 \uacfc\uc815\uc740 n\uc5d0\uc11c i\ub85c \ub098\ub204\uc5b4\uc9c8 \uc218 \uc788\ub294 \ub9cc\ud07c \ubc18\ubcf5\ub429\ub2c8\ub2e4.<\/li>\n
- \uacb0\uacfc \uc5c5\ub370\uc774\ud2b8:<\/strong> \ud604\uc7ac \uc18c\uc778\uc218 i\uc5d0 \ub300\ud574 result\ub97c \uc5c5\ub370\uc774\ud2b8\ud569\ub2c8\ub2e4. n\uc740 phi \ud568\uc218\uc758 \uc131\uc9c8\uc744 \ubc14\ud0d5\uc73c\ub85c \uc5c5\ub370\uc774\ud2b8 \ub429\ub2c8\ub2e4.<\/li>\n
- \ub0a8\uc740 \uc18c\uc778\uc218 \ucc98\ub9ac:<\/strong> \ubc18\ubcf5\uc774 \ub05d\ub09c \ud6c4, \ub9cc\uc57d n\uc774 1\ubcf4\ub2e4 \ud070 \uacbd\uc6b0(\uc18c\uc218\ub97c \ucc3e\uc740 \uacbd\uc6b0)\uc5d0\ub294 result\ub97c \ucd5c\uc885\uc801\uc73c\ub85c \uc5c5\ub370\uc774\ud2b8\ud569\ub2c8\ub2e4.<\/li>\n<\/ol>\n<\/section>\n\n
\ubcf5\uc7a1\ub3c4 \ubd84\uc11d<\/h2>\n
\uc774 \uc54c\uace0\ub9ac\uc998\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(\u221an)\uc785\ub2c8\ub2e4. \uc774\ub294 n\uc758 \uc18c\uc778\uc218\ub97c \ucc3e\uae30 \uc704\ud574 \uc774\uc911 \ub8e8\ud504 \uad6c\uc870\ub97c \uac00\uc84c\uae30 \ub54c\ubb38\uc785\ub2c8\ub2e4. \ucd5c\uc545\uc758 \uacbd\uc6b0 \uc18c\uc778\uc218\ub294 n\uc758 \uc81c\uacf1\uadfc\uae4c\uc9c0 \uac80\uc0ac\ud574\uc57c \ud558\uba70, \uc774 \uacfc\uc815\uc5d0\uc11c n\uc744 \uacc4\uc18d \ub098\ub204\uc5b4\uac00\ub294 \uc5f0\uc0b0\uc774 \uc788\uae30 \ub54c\ubb38\uc5d0, \uc804\uccb4\uc801\uc73c\ub85c \uad49\uc7a5\ud788 \ud6a8\uc728\uc801\uc778 \uc54c\uace0\ub9ac\uc998\uc785\ub2c8\ub2e4.<\/p>\n<\/section>\n\n\uacb0\ub860<\/h2>\n
\uc774 \uac15\uc88c\uc5d0\uc11c\ub294 \uc624\uc77c\ub7ec \ud53c \ud568\uc218\ub97c \uad6c\ud604\ud558\uc5ec \uc11c\ub85c\uc18c\uc758 \uac1c\uc218\ub97c \uacc4\uc0b0\ud558\ub294 \ubc29\ubc95\uc744 \ubc30\uc6e0\uc2b5\ub2c8\ub2e4. \uc774 \ubb38\uc81c\ub294 \ub2e4\uc591\ud55c \uc54c\uace0\ub9ac\uc998 \uc2dc\ud5d8\uc5d0\uc11c \ud754\ud788 \ucd9c\uc81c\ub418\ub294 \uc8fc\uc81c\uc774\uba70, \uc18c\uc778\uc218 \ubd84\ud574\ub97c \ud65c\uc6a9\ud558\uc5ec \ud6a8\uc728\uc801\uc73c\ub85c \ud574\uacb0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc2a4\uc704\ud504\ud2b8\ub97c \ud1b5\ud574 \uad6c\ud604\ud568\uc73c\ub85c\uc368 \ud504\ub85c\uadf8\ub798\ubc0d \uc2a4\ud0ac\uc744 \ud5a5\uc0c1\uc2dc\ud0a4\uace0, \uc54c\uace0\ub9ac\uc998\uc5d0 \ub300\ud55c \uae4a\uc740 \uc774\ud574\ub97c \ub3d5\uae30 \uc704\ud55c \uc88b\uc740 \uc5f0\uc2b5\uc774 \ub418\uc5c8\uae30\ub97c \ubc14\ub78d\ub2c8\ub2e4.<\/p>\n<\/section>\n