[알고리즘, 원리] 유클리드 호제법
정의 a = bx+r 일 때 (a,b) = (b,r) a와 b의 최대공약수는 b와 a를 b로 나눈 나머지의 최대공약수와 같다. 이를 이용하여 반복하면 두 수의 최대공약수를 쉽게 구할 수 있다. 구현 파이썬 (Python) def gcd(a,b): while b != 0: a, b = b, a%b return a 두 수에서 유클리드 호제법을 반복하여 최대공약수를 구하는 함수 def gcd(a, b): r = b % a if r == 0: return a return gcd(r, a) 재귀 함수를 이용한 구현 def gcd(*num_list): if len(num_list) == 1: return num_list[0] elif len(num_list) == 2: a, b = num_list[0], num_l..
2022. 9. 10.
[프로젝트 오일러] 문제7 - 10001번째 소수
문제 영문 By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 10 001st prime number? 바로가기 한글 소수를 크기 순으로 나열하면 2, 3, 5, 7, 11, 13, ... 과 같이 됩니다. 이 때 10,001번째의 소수를 구하세요. 바로가기 해설 파이썬 (Python) + 수학적 해석 방법 1 소수란 1또는 자기 자신으로밖에 나누어 떨어지지 않는 수를 뜻합니다. 그러니 자기 자신보다 작거나 같은 수로 모두 나눠본 다음, 자기 자신으로밖에 나누어지지 않는다면 그 수는 소수입니다! prime_th = 0 n = 1 while prime_th
2022. 9. 9.
