\ubb38\uc81c \uc124\uba85<\/h2>\n<\/header>\n\n\uc624\uc77c\ub7ec \ud53c \ud568\uc218(\u03c6(n))\ub294 \uc790\uc5f0\uc218 n\uc5d0 \ub300\ud574 n\uacfc \uc11c\ub85c \uc18c\uc778 \uc591\uc758 \uc815\uc218\uc758 \uac1c\uc218\ub97c \ub098\ud0c0\ub0c5\ub2c8\ub2e4. \uc608\ub97c \ub4e4\uc5b4, \u03c6(1) = 1, \u03c6(2) = 1, \u03c6(3) = 2, \u03c6(4) = 2, \u03c6(5) = 4\uc640 \uac19\uc740 \uacb0\uacfc\ub97c \ubcf4\uc5ec\uc90d\ub2c8\ub2e4. \uc774 \ubb38\uc81c\uc5d0\uc11c\ub294 \uc8fc\uc5b4\uc9c4 \uc790\uc5f0\uc218 n\uc5d0 \ub300\ud574 \u03c6(n)\ub97c \uacc4\uc0b0\ud558\ub294 \ud504\ub85c\uadf8\ub7a8\uc744 \uc791\uc131\ud558\ub294 \uac83\uc774 \ubaa9\ud45c\uc785\ub2c8\ub2e4.<\/p>\n<\/section>\n\n\ubb38\uc81c: \u03c6(n) \uacc4\uc0b0\ud558\uae30<\/h2>\n
\uc790\uc5f0\uc218 n\uc774 \uc8fc\uc5b4\uc84c\uc744 \ub54c, n\uc5d0 \ub300\ud574 \u03c6(n)\ub97c \uacc4\uc0b0\ud558\ub294 \uc790\ubc14 \ud504\ub85c\uadf8\ub7a8\uc744 \uc791\uc131\ud558\uc138\uc694. \ub2e8, n\uc740 1 \uc774\uc0c1 10^6 \uc774\ud558\uc758 \uc815\uc218\uc785\ub2c8\ub2e4.<\/p>\n
\uc785\ub825 \ud615\uc2dd<\/h3>\n\n- \uccab \uc904\uc5d0 \uc790\uc5f0\uc218 n\uc774 \uc8fc\uc5b4\uc9d1\ub2c8\ub2e4.<\/li>\n<\/ul>\n
\ucd9c\ub825 \ud615\uc2dd<\/h3>\n\n- n\uc5d0 \ub300\ud55c \u03c6(n)\uc758 \uac12\uc744 \ucd9c\ub825\ud569\ub2c8\ub2e4.<\/li>\n<\/ul>\n<\/section>\n
\n\ubb38\uc81c \ud480\uc774 \uacfc\uc815<\/h2>\n
\ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574\uc11c\ub294 \uc624\uc77c\ub7ec \ud53c \ud568\uc218\uc758 \uc815\uc758\uc640 \uc131\uc9c8\uc744 \uc815\ud655\ud788 \uc774\ud574\ud558\uace0, \uc774\ub97c \ud6a8\uc728\uc801\uc73c\ub85c \uacc4\uc0b0\ud558\ub294 \uc54c\uace0\ub9ac\uc998\uc744 \uc124\uacc4\ud574\uc57c \ud569\ub2c8\ub2e4.<\/p>\n
\uc624\uc77c\ub7ec \ud53c \ud568\uc218\uc758 \uc815\uc758<\/h3>\n
\uc624\uc77c\ub7ec \ud53c \ud568\uc218\ub294 \ub2e4\uc74c\uacfc \uac19\uc774 \uacc4\uc0b0\ub429\ub2c8\ub2e4:<\/p>\n
\n\u03c6(n) = n * (1 - 1\/p1) * (1 - 1\/p2) * ... * (1 - 1\/pk)\n <\/pre>\n\uc5ec\uae30\uc11c p1, p2, …, pk\ub294 n\uc758 \uace0\uc720 \uc18c\uc778\uc218\uc785\ub2c8\ub2e4. \uc989, n\uc744 \uc18c\uc778\uc218 \ubd84\ud574\ud55c \uacb0\uacfc\uc5d0 \ub4f1\uc7a5\ud558\ub294 \uc18c\uc218\uc758 \uac1c\uc218\uc640 \uadf8\ub4e4\uc758 \uacf1\uc744 \ud1b5\ud574 \uacb0\uacfc\ub97c \uad6c\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n
\uc18c\uc778\uc218 \ubd84\ud574\ub97c \ud1b5\ud55c \u03c6(n) \uacc4\uc0b0<\/h3>\n
\uc790\ubc14\uc5d0\uc11c \uc774 \ubc29\uc815\uc2dd\uc744 \uc0ac\uc6a9\ud558\uc5ec \u03c6(n)\ub97c \uacc4\uc0b0\ud558\uae30 \uc704\ud55c \ub2e8\uacc4\ub294 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4:<\/p>\n
\n- \uc785\ub825 \ubc1b\uc740 n\uc758 \ucd08\uae30 \uac12\uc744 \uc124\uc815\ud569\ub2c8\ub2e4.<\/li>\n
- 2\ubd80\ud130 n\uc758 \uc81c\uacf1\uadfc\uae4c\uc9c0 \ubc18\ubcf5\ud558\uba70 \uc18c\uc218\ub97c \ucc3e\uc2b5\ub2c8\ub2e4.<\/li>\n
- \uac01 \uc18c\uc218 p\uc5d0 \ub300\ud574 n\uc774 p\ub85c \ub098\ub258\uc5b4\uc9c0\ub294\uc9c0 \ud655\uc778\ud558\uace0, \ub098\ub258\uc5b4\uc9c0\uba74 n\uc744 p\ub85c \ub098\ub208 \ub2e4\uc74c, \u03c6(n)\uc5d0 (1 – 1\/p)\uc758 \uac12\uc744 \uacf1\ud569\ub2c8\ub2e4.<\/li>\n
- \ub9c8\uc9c0\ub9c9\uc73c\ub85c, n\uc774 1\uc774 \ub420 \ub54c\uae4c\uc9c0 \ubc18\ubcf5\ud569\ub2c8\ub2e4.<\/li>\n
- \uacc4\uc0b0\ud55c \u03c6(n)\uc758 \uac12\uc744 \ucd9c\ub825\ud569\ub2c8\ub2e4.<\/li>\n<\/ol>\n<\/section>\n
\n\uc790\ubc14 \ucf54\ub4dc \uc608\uc81c<\/h2>\n
\ub2e4\uc74c\uc740 \u03c6(n)\ub97c \uacc4\uc0b0\ud558\ub294 \uc790\ubc14 \ucf54\ub4dc\uc758 \uc608\uc81c\uc785\ub2c8\ub2e4:<\/p>\n
\nimport java.util.Scanner;\n\npublic class EulerTotient {\n public static void main(String[] args) {\n Scanner scanner = new Scanner(System.in);\n int n = scanner.nextInt();\n int originalN = n;\n double result = n;\n\n for (int i = 2; i * i <= n; i++) {\n if (n % i == 0) {\n while (n % i == 0) {\n n \/= i;\n }\n result *= (1.0 - (1.0 \/ (double)i));\n }\n }\n\n if (n > 1) {\n result *= (1.0 - (1.0 \/ (double)n));\n }\n\n System.out.println((int)result);\n }\n}\n <\/pre>\n\uc774 \ucf54\ub4dc\ub294 \uc0ac\uc6a9\uc790\uac00 \uc785\ub825\ud55c n\uc758 \uac12\uc5d0 \ub300\ud574 \u03c6(n)\ub97c \uacc4\uc0b0\ud558\uc5ec \ucd9c\ub825\ud569\ub2c8\ub2e4. \uc18c\uc218\ub85c \ub098\ub258\uc5b4\uc9c0\ub294 \uacbd\uc6b0\uc640 \ub098\ub204\uc5b4\uc9c4 \ud6c4 \uc751\ub2f5\ud558\ub294 \ubc29\uc2dd\uc73c\ub85c \u03c6(n)\uc744 \uacc4\uc0b0\ud558\uc600\uc2b5\ub2c8\ub2e4.<\/p>\n<\/section>\n\n\ud6a8\uc728\uc131 \ubd84\uc11d<\/h2>\n
\uc774 \uc54c\uace0\ub9ac\uc998\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(\u221an)\uc785\ub2c8\ub2e4. \uc65c\ub0d0\ud558\uba74 \uc18c\uc218\ub97c \ucc3e\uae30 \uc704\ud574 n\uc758 \uc81c\uacf1\uadfc\uae4c\uc9c0 \ubc18\ubcf5\ud574\uc57c \ud558\uae30 \ub54c\ubb38\uc785\ub2c8\ub2e4. \uc774 \ubc29\ubc95\uc740 n\uc758 \ud06c\uae30\uac00 \ucd5c\ub300 10^6\uc778 \uacbd\uc6b0\ub3c4 \ubb34\ub9ac \uc5c6\uc774 \ucc98\ub9ac\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \ub610\ud55c, \uacf5\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(1)\ub85c, \ucd94\uac00\uc801\uc778 \uba54\ubaa8\ub9ac \uc0ac\uc6a9\uc774 \ucd5c\uc18c\ud654\ub418\uc5b4 \uc788\uc5b4 \ud6a8\uc728\uc801\uc785\ub2c8\ub2e4.<\/p>\n<\/section>\n\n\uacb0\ub860<\/h2>\n
\uc624\uc77c\ub7ec \ud53c \ud568\uc218\ub294 \uc218\ub860\uacfc \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\uc5d0\uc11c \ub9e4\uc6b0 \uc911\uc694\ud55c \uac1c\ub150 \uc911 \ud558\ub098\uc785\ub2c8\ub2e4. \uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \uacfc\uc815\uc744 \ud1b5\ud574 \uc18c\uc218, \uc18c\uc778\uc218 \ubd84\ud574 \ubc0f \uae30\ubcf8\uc801\uc778 \uc218\ud559\uc801 \uc6d0\ub9ac\uc5d0 \ub300\ud55c \uc774\ud574\ub3c4\ub97c \ub192\uc77c \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc790\ubc14\ub97c \uc0ac\uc6a9\ud55c \ucf54\ub529\ud14c\uc2a4\ud2b8 \uc900\ube44\uc5d0 \uc720\uc6a9\ud55c \ubb38\uc81c\ub85c \uae30\uc5b5\ud558\uc2dc\uae30 \ubc14\ub78d\ub2c8\ub2e4.<\/p>\n<\/section>\n
\uc624\uc77c\ub7ec \ud53c \ud568\uc218(\u03c6(n))\ub294 \uc790\uc5f0\uc218 n\uc5d0 \ub300\ud574 n\uacfc \uc11c\ub85c \uc18c\uc778 \uc591\uc758 \uc815\uc218\uc758 \uac1c\uc218\ub97c \ub098\ud0c0\ub0c5\ub2c8\ub2e4. \uc608\ub97c \ub4e4\uc5b4, \u03c6(1) = 1, \u03c6(2) = 1, \u03c6(3) = 2, \u03c6(4) = 2, \u03c6(5) = 4\uc640 \uac19\uc740 \uacb0\uacfc\ub97c \ubcf4\uc5ec\uc90d\ub2c8\ub2e4. \uc774 \ubb38\uc81c\uc5d0\uc11c\ub294 \uc8fc\uc5b4\uc9c4 \uc790\uc5f0\uc218 n\uc5d0 \ub300\ud574 \u03c6(n)\ub97c \uacc4\uc0b0\ud558\ub294 \ud504\ub85c\uadf8\ub7a8\uc744 \uc791\uc131\ud558\ub294 \uac83\uc774 \ubaa9\ud45c\uc785\ub2c8\ub2e4.<\/p>\n<\/section>\n \uc790\uc5f0\uc218 n\uc774 \uc8fc\uc5b4\uc84c\uc744 \ub54c, n\uc5d0 \ub300\ud574 \u03c6(n)\ub97c \uacc4\uc0b0\ud558\ub294 \uc790\ubc14 \ud504\ub85c\uadf8\ub7a8\uc744 \uc791\uc131\ud558\uc138\uc694. \ub2e8, n\uc740 1 \uc774\uc0c1 10^6 \uc774\ud558\uc758 \uc815\uc218\uc785\ub2c8\ub2e4.<\/p>\n \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574\uc11c\ub294 \uc624\uc77c\ub7ec \ud53c \ud568\uc218\uc758 \uc815\uc758\uc640 \uc131\uc9c8\uc744 \uc815\ud655\ud788 \uc774\ud574\ud558\uace0, \uc774\ub97c \ud6a8\uc728\uc801\uc73c\ub85c \uacc4\uc0b0\ud558\ub294 \uc54c\uace0\ub9ac\uc998\uc744 \uc124\uacc4\ud574\uc57c \ud569\ub2c8\ub2e4.<\/p>\n \uc624\uc77c\ub7ec \ud53c \ud568\uc218\ub294 \ub2e4\uc74c\uacfc \uac19\uc774 \uacc4\uc0b0\ub429\ub2c8\ub2e4:<\/p>\n \uc5ec\uae30\uc11c p1, p2, …, pk\ub294 n\uc758 \uace0\uc720 \uc18c\uc778\uc218\uc785\ub2c8\ub2e4. \uc989, n\uc744 \uc18c\uc778\uc218 \ubd84\ud574\ud55c \uacb0\uacfc\uc5d0 \ub4f1\uc7a5\ud558\ub294 \uc18c\uc218\uc758 \uac1c\uc218\uc640 \uadf8\ub4e4\uc758 \uacf1\uc744 \ud1b5\ud574 \uacb0\uacfc\ub97c \uad6c\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n \uc790\ubc14\uc5d0\uc11c \uc774 \ubc29\uc815\uc2dd\uc744 \uc0ac\uc6a9\ud558\uc5ec \u03c6(n)\ub97c \uacc4\uc0b0\ud558\uae30 \uc704\ud55c \ub2e8\uacc4\ub294 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4:<\/p>\n \ub2e4\uc74c\uc740 \u03c6(n)\ub97c \uacc4\uc0b0\ud558\ub294 \uc790\ubc14 \ucf54\ub4dc\uc758 \uc608\uc81c\uc785\ub2c8\ub2e4:<\/p>\n \uc774 \ucf54\ub4dc\ub294 \uc0ac\uc6a9\uc790\uac00 \uc785\ub825\ud55c n\uc758 \uac12\uc5d0 \ub300\ud574 \u03c6(n)\ub97c \uacc4\uc0b0\ud558\uc5ec \ucd9c\ub825\ud569\ub2c8\ub2e4. \uc18c\uc218\ub85c \ub098\ub258\uc5b4\uc9c0\ub294 \uacbd\uc6b0\uc640 \ub098\ub204\uc5b4\uc9c4 \ud6c4 \uc751\ub2f5\ud558\ub294 \ubc29\uc2dd\uc73c\ub85c \u03c6(n)\uc744 \uacc4\uc0b0\ud558\uc600\uc2b5\ub2c8\ub2e4.<\/p>\n<\/section>\n \uc774 \uc54c\uace0\ub9ac\uc998\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(\u221an)\uc785\ub2c8\ub2e4. \uc65c\ub0d0\ud558\uba74 \uc18c\uc218\ub97c \ucc3e\uae30 \uc704\ud574 n\uc758 \uc81c\uacf1\uadfc\uae4c\uc9c0 \ubc18\ubcf5\ud574\uc57c \ud558\uae30 \ub54c\ubb38\uc785\ub2c8\ub2e4. \uc774 \ubc29\ubc95\uc740 n\uc758 \ud06c\uae30\uac00 \ucd5c\ub300 10^6\uc778 \uacbd\uc6b0\ub3c4 \ubb34\ub9ac \uc5c6\uc774 \ucc98\ub9ac\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \ub610\ud55c, \uacf5\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(1)\ub85c, \ucd94\uac00\uc801\uc778 \uba54\ubaa8\ub9ac \uc0ac\uc6a9\uc774 \ucd5c\uc18c\ud654\ub418\uc5b4 \uc788\uc5b4 \ud6a8\uc728\uc801\uc785\ub2c8\ub2e4.<\/p>\n<\/section>\n \uc624\uc77c\ub7ec \ud53c \ud568\uc218\ub294 \uc218\ub860\uacfc \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\uc5d0\uc11c \ub9e4\uc6b0 \uc911\uc694\ud55c \uac1c\ub150 \uc911 \ud558\ub098\uc785\ub2c8\ub2e4. \uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \uacfc\uc815\uc744 \ud1b5\ud574 \uc18c\uc218, \uc18c\uc778\uc218 \ubd84\ud574 \ubc0f \uae30\ubcf8\uc801\uc778 \uc218\ud559\uc801 \uc6d0\ub9ac\uc5d0 \ub300\ud55c \uc774\ud574\ub3c4\ub97c \ub192\uc77c \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc790\ubc14\ub97c \uc0ac\uc6a9\ud55c \ucf54\ub529\ud14c\uc2a4\ud2b8 \uc900\ube44\uc5d0 \uc720\uc6a9\ud55c \ubb38\uc81c\ub85c \uae30\uc5b5\ud558\uc2dc\uae30 \ubc14\ub78d\ub2c8\ub2e4.<\/p>\n<\/section>\n\ubb38\uc81c: \u03c6(n) \uacc4\uc0b0\ud558\uae30<\/h2>\n
\uc785\ub825 \ud615\uc2dd<\/h3>\n
\n
\ucd9c\ub825 \ud615\uc2dd<\/h3>\n
\n
\ubb38\uc81c \ud480\uc774 \uacfc\uc815<\/h2>\n
\uc624\uc77c\ub7ec \ud53c \ud568\uc218\uc758 \uc815\uc758<\/h3>\n
\n\u03c6(n) = n * (1 - 1\/p1) * (1 - 1\/p2) * ... * (1 - 1\/pk)\n <\/pre>\n
\uc18c\uc778\uc218 \ubd84\ud574\ub97c \ud1b5\ud55c \u03c6(n) \uacc4\uc0b0<\/h3>\n
\n
\uc790\ubc14 \ucf54\ub4dc \uc608\uc81c<\/h2>\n
\nimport java.util.Scanner;\n\npublic class EulerTotient {\n public static void main(String[] args) {\n Scanner scanner = new Scanner(System.in);\n int n = scanner.nextInt();\n int originalN = n;\n double result = n;\n\n for (int i = 2; i * i <= n; i++) {\n if (n % i == 0) {\n while (n % i == 0) {\n n \/= i;\n }\n result *= (1.0 - (1.0 \/ (double)i));\n }\n }\n\n if (n > 1) {\n result *= (1.0 - (1.0 \/ (double)n));\n }\n\n System.out.println((int)result);\n }\n}\n <\/pre>\n\ud6a8\uc728\uc131 \ubd84\uc11d<\/h2>\n
\uacb0\ub860<\/h2>\n