\ucf54\ub529 \ud14c\uc2a4\ud2b8\ub294 \ud604\ub300 \uc18c\ud504\ud2b8\uc6e8\uc5b4 \uacf5\ud559\uc5d0\uc11c \ub9e4\uc6b0 \uc911\uc694\ud55c \ubd80\ubd84\uc785\ub2c8\ub2e4. \ub9ce\uc740 \uae30\uc5c5\ub4e4\uc774 \uae30\uc220 \uba74\uc811\uc5d0 \ucf54\ub529 \ubb38\uc81c\ub97c \ud3ec\ud568\uc2dc\ucf1c, \uc9c0\uc6d0\uc790\uc758 \uc54c\uace0\ub9ac\uc998 \ubc0f \ubb38\uc81c \ud574\uacb0 \ub2a5\ub825\uc744 \ud3c9\uac00\ud569\ub2c8\ub2e4. \uc774\ubc88 \uac15\uc88c\uc5d0\uc11c\ub294 \uc218\ud559\uc801 \uac1c\ub150\uc778 \uc624\uc77c\ub7ec \ud53c(Euler’s Totient Function)\uc5d0 \ub300\ud574 \uc54c\uc544\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n
\uc624\uc77c\ub7ec \ud53c \ud568\uc218\ub294 \uc815\uc218 n\uc758 \uc591\uc758 \uc815\uc218 m\uc758 \uac1c\uc218\ub97c \ubc18\ud658\ud569\ub2c8\ub2e4. m\uc740 1 \uc774\uc0c1 n \uc774\ud558\uc758 \uc815\uc218\uc774\uba70, m\uacfc n\uc774 \uc11c\ub85c \uc18c\uc778 \uc815\uc218\uc785\ub2c8\ub2e4. \uc989, gcd(m, n) = 1\uc744 \ub9cc\uc871\ud558\ub294 m\uc758 \uac1c\uc218\ub97c \uad6c\ud558\ub294 \uac83\uc774 \ubaa9\ud45c\uc785\ub2c8\ub2e4.<\/p>\n
\ubb38\uc81c:<\/strong> \uc8fc\uc5b4\uc9c4 \uc815\uc218 n\uc5d0 \ub300\ud574 \uc624\uc77c\ub7ec \ud53c \ud568\uc218\ub97c \uacc4\uc0b0\ud558\uc2dc\uc624.<\/p>\n \uc785\ub825:<\/p>\n \ucd9c\ub825:<\/p>\n \uc624\uc77c\ub7ec \ud53c \ud568\uc218\ub294 \ub2e4\uc74c\uacfc \uac19\uc774 \uc815\uc758\ub429\ub2c8\ub2e4:<\/p>\n \uc774\ub97c \ud1b5\ud574, n\uc758 \uc18c\uc778\uc218\ub97c \ucc3e\uc544 \uadf8\uc5d0 \ub9de\uac8c \u03d5(n)\ub97c \uacc4\uc0b0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n \uc774\uc81c \uc624\uc77c\ub7ec \ud53c \ud568\uc218\ub97c C#\uc744 \uc0ac\uc6a9\ud558\uc5ec \uad6c\ud604\ud574\ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uc774 \uc54c\uace0\ub9ac\uc998\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(\u221an)\uc73c\ub85c, n\uc758 \uc18c\uc778\uc218\ub97c \ucc3e\uc544\ub0b4\ub294\ub370 \ud6a8\uc728\uc801\uc785\ub2c8\ub2e4.<\/p>\n \uc704\uc758 \ucf54\ub4dc\ub294 \uc624\uc77c\ub7ec \ud53c \ud568\uc218\ub97c \uacc4\uc0b0\ud558\uae30 \uc704\ud55c \uac83\uc73c\ub85c, \ub2e4\uc74c\uacfc \uac19\uc740 \ub2e8\uacc4\ub85c \uad6c\uc131\ub429\ub2c8\ub2e4:<\/p>\n \uc774 \uc54c\uace0\ub9ac\uc998\uc740 \uc8fc\uc5b4\uc9c4 \ubc94\uc704 \ub0b4\uc5d0\uc11c \ub9e4\uc6b0 \ube60\ub974\uac8c \ub3d9\uc791\ud569\ub2c8\ub2e4. \ud558\uc9c0\ub9cc \ub2e4\uc591\ud55c \uc785\ub825\uc5d0 \ub300\ud574 \ube60\ub978 \uacc4\uc0b0\uc744 \uc704\ud574, \ubbf8\ub9ac \uc18c\uc218\ub97c \uad6c\ud574\ub458 \uc218\ub3c4 \uc788\uc2b5\ub2c8\ub2e4. \uc5d0\ub77c\ud1a0\uc2a4\ud14c\ub124\uc2a4\uc758 \uccb4\ub97c \ud1b5\ud574 \uc18c\uc218\ub97c \uad6c\ud558\uace0 \ud574\ub2f9 \uc18c\uc218\ub97c \uc774\uc6a9\ud558\uc5ec \uc624\uc77c\ub7ec \ud53c \uac12\uc744 \uacc4\uc0b0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n \uc18c\uc218\ub4e4\uc744 \uc800\uc7a5\ud558\ub294 \ubc30\uc5f4\uc744 \uc774\uc6a9\ud558\uc5ec \ud568\uc218\ub97c \uc870\uae08 \ub354 \uac1c\uc120\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc774 \ubc29\ubc95\uc740 \ub2e4\ub978 \uc218\ub4e4\uacfc\uc758 \ube44\uad50\ub97c \ud1b5\ud574 \uc18d\ub3c4\uac00 \uc62c\ub77c\uac00\uace0, \uba54\ubaa8\ub9ac \uc0ac\uc6a9\ub3c4 \ucd5c\uc801\ud654\ub420 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n \uc624\uc77c\ub7ec \ud53c \ud568\uc218\ub294 \uba54\ub2c8\uc9c0\ub4dc \uc5b8\uc5b4\uc778 C#\uc5d0\uc11c\ub3c4 \uac04\ub2e8\ud788 \uad6c\ud604\ud560 \uc218 \uc788\uc73c\uba70, \uc774\ub860\uacfc \ucf54\ub4dc\uc758 \uacb0\ud569\uc744 \ud1b5\ud574 \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ub97c \ubcf4\ub2e4 \ud6a8\uc728\uc801\uc73c\ub85c \ud574\uacb0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc774\ubc88 \uac15\uc88c\ub97c \ud1b5\ud574 C#\uc758 \uae30\ucd08\uc801\uc778 \ud568\uc218, \uc720\ud074\ub9ac\ub4dc \ud638\uc81c\ubc95\uc744 \uc774\uc6a9\ud55c \ucd5c\ub300\uacf5\uc57d\uc218 \uad6c\ud558\uae30 \ub4f1 \ub2e4\uc591\ud55c \uae30\uc220\uc744 \ud65c\uc6a9\ud558\uc5ec \uc624\uc77c\ub7ec \ud53c\ub97c \uad6c\ud558\ub294 \ubc29\ubc95\uc744 \ud559\uc2b5\ud558\uc168\uc2b5\ub2c8\ub2e4.<\/p>\n \uc55e\uc73c\ub85c\uc758 \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c \ub354 \ub9ce\uc740 \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574 \uafb8\uc900\ud788 \uc5f0\uc2b5\ud558\uc2dc\uae38 \ubc14\ub78d\ub2c8\ub2e4!<\/p>\n <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"\uc785\ub825 \ud615\uc2dd<\/h3>\n
\n
\ucd9c\ub825 \ud615\uc2dd<\/h3>\n
\n
\uc608\uc81c<\/h3>\n
6<\/code><\/pre>\n2<\/code><\/pre>\n<\/div>\n\uc774\ub860\uc801 \ubc30\uacbd<\/h2>\n
\n
C# \uad6c\ud604<\/h2>\n
using System;\n\nclass Program\n{\n static void Main()\n {\n int n = int.Parse(Console.ReadLine());\n Console.WriteLine(EulerPhi(n));\n }\n\n static int EulerPhi(int n)\n {\n int result = n; \/\/ \ucd08\uae30\uac12\uc744 n\uc73c\ub85c \uc124\uc815\n for (int p = 2; p * p <= n; p++)\n {\n \/\/ p\uac00 n\uc758 \uc18c\uc778\uc218\uc778\uc9c0 \ud655\uc778\n if (n % p == 0)\n {\n \/\/ p\ub85c n\uc744 \ub098\ub220\uc11c \uc18c\uc778\uc218\ub97c \uc81c\uac70\n while (n % p == 0)\n {\n n \/= p;\n }\n result -= result \/ p; \/\/ \uc624\uc77c\ub7ec \ud53c \uacf5\uc2dd \uc801\uc6a9\n }\n }\n \/\/ \ub0a8\uc740 n\uc774 \uc18c\uc218\uc778 \uacbd\uc6b0\n if (n > 1)\n {\n result -= result \/ n;\n }\n\n return result; \/\/ \ucd5c\uc885 \uacb0\uacfc \ubc18\ud658\n }\n}\n<\/code><\/pre>\n\ucf54\ub4dc \uc124\uba85<\/h2>\n
\n
\uc131\ub2a5 \ucd5c\uc801\ud654<\/h2>\n
\uacb0\ub860<\/h2>\n