[알고리즘 #6] 최대공약수 최소공배수 구하는 알고리즘 정리
** Responsive Ad ** 1. 최대공약수 (Greatest Common Factor, GCF) 두 개 이상의 수가 공통으로 가지고 있는 약수 중 가장 큰 수 8의 약수 : 1, 2, 4, 8 12의 약수 : 1, 2, 3, 4, 6, 12 8과 12의 최대공약수 : 4 2. 최소공배수 (the Least Common Multiple, LCM) 두 개 이상의 수가 공통으로 가지는 배수 중 가장 작은 수 3의 배수 : 3, 6, 9, 12, 15.. 5의 배수 5, 10, 15, 20.. 3과 5의 최소공배수 : 15 3. 서로소 (relative prime) 1 외의 공약수를 갖지 않는 두 수 ex) 7, 11 는 1 외의 공약수가 없으므로 서로소이다. 4. 최대공약수 구하는 알고리즘 1) 유클..
2017. 3. 22.
[알고리즘 #4] 약수(divisor) 구하는 알고리즘 정리
** Responsive Ad ** 1. 약수 (divisor, aliquot)어떤 수를 나누었을 때 나머지가 0이 되는 수, 제수(除數) 2. N의 약수를 구하기 위한 접근방법 1) 1부터 N까지 차례로 나누어 나머지가 0이 되는지 확인 2) sqrt(N) 보다 작은 약수를 먼저 구한 뒤 이를 이용하여 sqrt(N) 보다 큰 약수 구하기 100의 약수는 1, 2, 4, 5, 10, 20, 25, 50, 100 sqrt(100) = 10 이므로 1,2,4,5 를 구한 뒤,100 / 1 = 100100 / 2 = 50100 / 4 = 25100 / 5 = 20 으로 sqrt(100)보다 큰 약수를 구한다. ** 큰사각형 광고 **
2017. 3. 22.
[알고리즘 #3] 소수 판별 알고리즘
** 반응형 광고 ** 1. 소수 (prime number) 란? 1과 자기 자신만을 약수로 가지는 수로 1보다 큰 수 (2, 3, 5, 7, 11, 13 ..) 2. 소수 판별법 1) 나머지가 0인 수 검사어떤 수 A가 소수인지 판별하기 위해서는 A를 2부터 A보다 1작은 수까지 나누어서 나머지가 0인 경우가 있는지 검사함.MOD(A, 2) ~ MOD(A, A-1) = 0 인 경우를 check 2) 제곱근 이용 어떤 수 A의 제곱근까지의 수 중 한 개의 수에 대해서라도 나누어 떨어지면 소수가 아님.MOD(A, 2) ~ MOD(A, SQRT(A)) = 0 인 경우를 check당연히, 1) 의 방식보다 성능이 좋다. 3. 에라토스테네스의 체 1~N 까지의 수 중에서 소수를 구하고자 한다면 에라토스테네스의 ..
2017. 3. 16.
