소수

[삼성SDS] 24년 하반기 대학생 알고리즘 특강(Day5) : 정수론(유클리드 호제법, 확장 유클리드 호제법, 소수), 조합론

유클리드 호제법빠른 시간에 두수의 최대공약수를 구할 수 있는 방법이다.2개의 자연수의 최대공약수를 구하는 알고리즘의 하나이다.2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a > b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 성질을 이용한다.gcd(a, b) = gcd(b, r) 공식 대입해보기a = 36, b = 24gcd(a, b) = gcd(b, a % b)gcd(36, 24)= gcd(24, 12)= gcd(12, 0)r == 0 일 때, b가 최대공약수가 된다. 예제문제백준 14476번 : 최대공약수 하나빼기 https://www.acmicpc.net/problem/14476 최대공약수 구하는 메소드// gcd(a, b) == gcd(b, r) : r ..