\ub450 \uac1c\uc758 \uc815\uc218 \ucd5c\ub300 \uacf5\uc57d\uc218\ub97c \uad6c\ud558\ub294 \ubc29\ubc95\uc740 \uc5ec\ub7ec \uac00\uc9c0\uac00 \uc788\uc9c0\ub9cc, \uc720\uba85\ud55c \uc720\ud074\ub9ac\ub4dc \uc54c\uace0\ub9ac\uc998<\/strong>\uc744 \ud65c\uc6a9\ud558\uba74 \ud6a8\uc728\uc801\uc73c\ub85c \ud574\uacb0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc720\ud074\ub9ac\ub4dc \uc54c\uace0\ub9ac\uc998\uc740 \ub2e4\uc74c\uc758 \ub2e8\uacc4\ub85c \uc791\ub3d9\ud569\ub2c8\ub2e4:<\/p>\n \uc720\ud074\ub9ac\ub4dc \uc54c\uace0\ub9ac\uc998\uc744 \uc790\ubc14\uc2a4\ud06c\ub9bd\ud2b8\ub85c \uad6c\ud604\ud55c \ucf54\ub4dc\ub294 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4:<\/p>\n \uc720\ud074\ub9ac\ub4dc \uc54c\uace0\ub9ac\uc998\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(log(min(a, b)))\uc785\ub2c8\ub2e4. \ucd5c\ub300 \uacf5\uc57d\uc218\ub97c \uad6c\ud558\ub294 \ubc29\ubc95\uc5d0 \uc775\uc219\ud574\uc84c\ub2e4\uba74, \uc544\ub798\uc758 \ubb38\uc81c\ub97c \ud480\uc5b4\ubcf4\uc138\uc694:<\/p>\n \uc774\ubc88 \uae00\uc5d0\uc11c\ub294 \uc790\ubc14\uc2a4\ud06c\ub9bd\ud2b8\ub97c \uc774\uc6a9\ud558\uc5ec \ucd5c\ub300 \uacf5\uc57d\uc218\ub97c \uad6c\ud558\ub294 \ubb38\uc81c\ub97c \ud574\uacb0\ud574 \ubcf4\uc558\uc2b5\ub2c8\ub2e4.a<\/code>\uc640 b<\/code>\uac00 \uc8fc\uc5b4\uc9c8 \ub54c, \ub450 \uc218\uc758 \ucd5c\ub300 \uacf5\uc57d\uc218(GCD)\ub97c \uad6c\ud558\ub294 \ud568\uc218\ub97c \uc791\uc131\ud558\uc138\uc694.
\n \ucd5c\ub300 \uacf5\uc57d\uc218\ub294 \ub450 \uc218\uc758 \uacf5\ud1b5\ub41c \uc57d\uc218 \uc911 \uac00\uc7a5 \ud070 \uc218\ub97c \uc758\ubbf8\ud569\ub2c8\ub2e4.<\/p>\n\uc785\ub825 \ubc0f \ucd9c\ub825 \ud615\uc2dd<\/h3>\n
\n
a<\/code>, b<\/code> (1 \u2264 a<\/code>, b<\/code> \u2264 109<\/sup>)<\/li>\n\uc608\uc2dc<\/h3>\n
\n \uc785\ub825: 48, 18\n \ucd9c\ub825: 6\n <\/pre>\n
\ubb38\uc81c \uc811\uadfc \ubc29\ubc95<\/h3>\n
\n \uc774 \uc54c\uace0\ub9ac\uc998\uc740 \ub2e4\uc74c\uacfc \uac19\uc740 \uae30\ubcf8 \uc6d0\ub9ac\ub97c \uac00\uc9c0\uace0 \uc788\uc2b5\ub2c8\ub2e4:<\/p>\n\n
a<\/code>\uc640 b<\/code>\uc758 \ucd5c\ub300 \uacf5\uc57d\uc218\ub294 b<\/code>\uac00 0\uc774 \ub420 \ub54c\uae4c\uc9c0 \ubc18\ubcf5\uc801\uc73c\ub85c a % b<\/code>\ub97c \uad6c\ud558\uc5ec \uad6c\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/li>\na<\/code>, b<\/code>) = GCD(b<\/code>, a % b<\/code>)\uc774\uba70, b<\/code>\uac00 0\uc774 \ub420 \ub54c a<\/code>\uac00 \ucd5c\ub300 \uacf5\uc57d\uc218\uc785\ub2c8\ub2e4.<\/li>\n<\/ul>\n\uc720\ud074\ub9ac\ub4dc \uc54c\uace0\ub9ac\uc998 \uc124\uba85<\/h3>\n
\n
a<\/code>\uc640 b<\/code>\ub97c \uc900\ube44\ud569\ub2c8\ub2e4. \ub9cc\uc57d b<\/code>\uac00 0\uc774 \uc544\ub2c8\uba74, \ub2e4\uc74c \ub2e8\uacc4\ub97c \uc9c4\ud589\ud569\ub2c8\ub2e4.<\/li>\nr = a % b<\/code>\ub97c \uacc4\uc0b0\ud558\uc5ec \uc0c8\ub85c\uc6b4 \ub098\uba38\uc9c0\ub97c \uad6c\ud569\ub2c8\ub2e4.<\/li>\na<\/code>\uc758 \uac12\uc740 b<\/code>\ub85c, b<\/code>\uc758 \uac12\uc740 r<\/code>\ub85c \uc5c5\ub370\uc774\ud2b8\ud569\ub2c8\ub2e4.<\/li>\nb<\/code>\uac00 0\uc77c \ub54c\uae4c\uc9c0 \ubc18\ubcf5\ud569\ub2c8\ub2e4.<\/li>\na<\/code>\uac00 \ucd5c\ub300 \uacf5\uc57d\uc218\uac00 \ub429\ub2c8\ub2e4.<\/li>\n<\/ol>\n\uc790\ubc14\uc2a4\ud06c\ub9bd\ud2b8 \uad6c\ud604<\/h3>\n
\n function gcd(a, b) {\n while (b !== 0) {\n const r = a % b;\n a = b;\n b = r;\n }\n return a;\n }\n\n \/\/ \ud14c\uc2a4\ud2b8\n const result = gcd(48, 18);\n console.log(result); \/\/ 6\n <\/pre>\n\uc2dc\uac04 \ubcf5\uc7a1\ub3c4 \ubd84\uc11d<\/h3>\n
\n \uc774\ub294 \ub450 \uc218\uc758 \ube44\uc728\uc5d0 \ub530\ub77c \uc131\ub2a5\uc774 \uc88b\uc740 \ud3b8\uc774\uba70, \ud2b9\ud788 \ud070 \uc218\ub97c \ub2e4\ub8f0 \ub54c \ud6a8\uc728\uc801\uc778 \ubc29\ubc95\uc785\ub2c8\ub2e4.<\/p>\n\ucd94\uac00 \ubb38\uc81c \ubc0f \uc5f0\uc2b5<\/h3>\n
\n
\uacb0\ub860<\/h3>\n
\n \uc720\ud074\ub9ac\ub4dc \uc54c\uace0\ub9ac\uc998\uc744 \ud1b5\ud574 \ud6a8\uc728\uc801\uc778 \ubb38\uc81c \ud574\uacb0 \ubc29\uc548\uc744 \uc775\ud790 \uc218 \uc788\uc5c8\uc2b5\ub2c8\ub2e4.
\n \uc774\ub7ec\ud55c \uae30\ubcf8\uc801\uc778 \uc54c\uace0\ub9ac\uc998\ub4e4\uc740 \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc640 \uc2e4\ubb34\uc5d0\uc11c \uc790\uc8fc \uc0ac\uc6a9\ub418\ubbc0\ub85c, \ucda9\ubd84\ud55c \uc5f0\uc2b5\uc774 \ud544\uc694\ud569\ub2c8\ub2e4.<\/p>\n\ucc38\uace0 \uc790\ub8cc<\/h3>\n