{"id":27130,"date":"2024-10-27T13:43:55","date_gmt":"2024-10-27T13:43:55","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=27130"},"modified":"2024-11-26T07:21:56","modified_gmt":"2024-11-26T07:21:56","slug":"%ed%8c%8c%ec%9d%b4%ec%8d%ac-%ec%bd%94%eb%94%a9%ed%85%8c%ec%8a%a4%ed%8a%b8-%ea%b0%95%ec%a2%8c-%ec%98%a4%ec%9d%bc%eb%9f%ac-%ed%94%bc","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/27130\/","title":{"rendered":"\ud30c\uc774\uc36c \ucf54\ub529\ud14c\uc2a4\ud2b8 \uac15\uc88c, \uc624\uc77c\ub7ec \ud53c"},"content":{"rendered":"

<\/p>\n

\n<\/header>\n
\n

\ubb38\uc81c \uc124\uba85<\/h2>\n

\n \uc624\uc77c\ub7ec\uc758 \ud53c \ud568\uc218(Euler’s totient function) \u03c6(n)\uc740 1\ubd80\ud130 n\uae4c\uc9c0\uc758
\n \uc815\uc218 \uc911 n\uacfc \uc11c\ub85c\uc18c\uc778 \uc218\uc758 \uac1c\uc218\ub97c \uc13c \ud568\uc218\uc785\ub2c8\ub2e4. \uc608\ub97c \ub4e4\uc5b4,
\n \u03c6(1)=1, \u03c6(2)=1, \u03c6(3)=2, \u03c6(4)=2, \u03c6(5)=4\uc785\ub2c8\ub2e4.\n <\/p>\n

\n \uc8fc\uc5b4\uc9c4 \uc591\uc758 \uc815\uc218 n\uc5d0 \ub300\ud574 \u03c6(n) \uac12\uc744 \uacc4\uc0b0\ud558\ub294 \ucf54\ub4dc\ub97c \uc791\uc131\ud558\uc2dc\uc624.
\n \ub2e8, n\uc740 1\uacfc 10^6 \uc0ac\uc774\uc758 \uac12\uc785\ub2c8\ub2e4.\n <\/p>\n

\ubb38\uc81c \ud574\uacb0 \uacfc\uc815<\/h2>\n

1. \ubb38\uc81c \uc774\ud574\ud558\uae30<\/h3>\n

\n \uc774 \ubb38\uc81c\ub294 \uc624\uc77c\ub7ec\uc758 \ud53c \ud568\uc218\uc758 \uc815\uc758\ub97c \uae30\ubc18\uc73c\ub85c \ud558\uba70,
\n n\uacfc \uc11c\ub85c\uc18c\uc778 \ubaa8\ub4e0 \uc218\ub97c \ucc3e\uc544\uc57c \ud569\ub2c8\ub2e4. \uc11c\ub85c\uc18c\ub780 \ub450 \uc218\uc758
\n \ucd5c\ub300\uacf5\uc57d\uc218\uac00 1\uc778 \uac83\uc744 \ub9d0\ud558\uba70, \uc774 \uc870\uac74\uc744 \uc774\uc6a9\ud574
\n \u03c6(n)\uc744 \uad6c\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n <\/p>\n

2. \uc54c\uace0\ub9ac\uc998 \uc124\uacc4<\/h3>\n

\n \uc624\uc77c\ub7ec \ud53c \ud568\uc218\ub294 \uae30\uc57d\ubd84\uc218\uc758 \ud615\ud0dc\ub85c \ud45c\ud604\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc774\ub97c \ud1b5\ud574 n\uc758 \uc18c\uc778\uc218\ub97c \ucc3e\uc544
\n \uc11c\ub85c\uc18c\uc758 \uac1c\uc218\ub97c \uad6c\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. n\uc758 \uc18c\uc778\uc218 p\uc5d0 \ub300\ud558\uc5ec,
\n \u03c6(n) = n \u00d7 (1 – 1\/p)\uc785\ub2c8\ub2e4. n\uc758 \ubaa8\ub4e0 \uc18c\uc778\uc218\uc5d0 \ub300\ud574 \uc774 \uc2dd\uc744 \uc801\uc6a9\ud558\uba74 \ub429\ub2c8\ub2e4.\n <\/p>\n

3. \ucf54\ub4dc \uad6c\ud604<\/h3>\n

\n \uba3c\uc800 \uc18c\uc778\uc218\ub97c \ucc3e\ub294 \ud568\uc218\ub97c \uad6c\ud604\ud55c \ud6c4, \uc774\ub97c \uc774\uc6a9\ud574
\n \u03c6(n)\uc744 \uacc4\uc0b0\ud558\ub294 \ucf54\ub4dc\ub97c \uc791\uc131\ud558\uaca0\uc2b5\ub2c8\ub2e4.\n <\/p>\n

\ndef euler_totient(n):\n    result = n   # \ucd08\uae30\uac12\uc740 n\n    p = 2\n    while p * p <= n:   # \uc18c\uc778\uc218\ub97c \ucc3e\uae30\n        if n % p == 0:   # p\uac00 n\uc758 \uc18c\uc778\uc218\uc778\uc9c0 \ud655\uc778\n            while n % p == 0:   # p\uc5d0 \ud574\ub2f9\ud558\ub294 \uc18c\uc778\uc218\ub97c \uc81c\uac70\n                n \/\/= p\n            result -= result \/\/ p   # \uc11c\ub85c\uc18c \uac1c\uc218 \uacc4\uc0b0\n        p += 1\n    if n > 1:   # \ub9c8\uc9c0\ub9c9\uc73c\ub85c \ub0a8\uc740 \uc18c\uc778\uc218\n        result -= result \/\/ n\n    return result\n        <\/code><\/pre>\n
4. \uc608\uc81c\uc640 \ud14c\uc2a4\ud2b8<\/h3>\n
\n            \u03c6(10)\uc744 \uacc4\uc0b0\ud574\ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \u03c6(10)\uc740 5\uc640 2\uc758 \uc18c\uc778\uc218\ub97c \uac00\uc9d1\ub2c8\ub2e4.
\n            \uc774\ub97c \ud1b5\ud574 \u03c6(10) = 10 \u00d7 (1 – 1\/2) \u00d7 (1 – 1\/5) = 4\uac00 \ub429\ub2c8\ub2e4.\n        <\/p>\n
\nprint(euler_totient(10))  # \ucd9c\ub825: 4\n        <\/code><\/pre>\n
5. \uacb0\ub860<\/h3>\n
\n            \uc624\uc77c\ub7ec \ud53c \ud568\uc218\ub294 \uc218\ub860\uc5d0\uc11c \ub9e4\uc6b0 \uc911\uc694\ud55c \uac1c\ub150\uc73c\ub85c,
\n            \uace0\uae09 \uc54c\uace0\ub9ac\uc998\uc744 \uad6c\ud604\ud558\ub294 \ub370 \uc788\uc5b4 \ud544\uc218\uc801\uc778 \uc9c0\uc2dd\uc744 \uc81c\uacf5\ud569\ub2c8\ub2e4.
\n            \uc774 \ubb38\uc81c\ub97c \ud1b5\ud574 \uc774\ub7ec\ud55c \uae30\ubc18 \uc9c0\uc2dd\uc744 \ud655\ub9bd\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n        <\/p>\n<\/article>\n