{Programing}/{Math}3 최대 공약수, 최소 공배수 최대 공약수(GCD : Greatest Common Divisor) 두 수의 공약수중 가장 큰 수 첫번째 방법. 2부터 둘 중 작은 수까지 계속 나눠 보는 방법 두번째 방법. 유클리드 호제법 : gcd(a,b) = gcd(b, a%b) 임을 이용. 최소 공배수(LCM : Least Common Multiple) 두수의 공배수중 제일 작은 수 최대 공약수를 이용해 구하는 방법. lcm(a,b) = ab/g ( g = gcm(a,b) ) 오버플로우를 조심. a/g * b/g *g 같은 방식으로 구하면 조금 덜 수 있다. 2020. 3. 10. 소수 판별 소수(Prime Number) : 1과 자기 자신으로만 나누어 떨어지는 수. 암호 분야에서 기술적으로 이용하고 있는 중요한 수. 임의의 수 N의 소수 구하기. 첫번째 방법 2~N-1까지 모든 수로 나누어 보면서 나머지가 0인 경우가 있는지 판단하는 방법. 0인 경우가 한번이라도 있으면 소수가 아님. 두번째 방법. 2~ N의 제곱근 까지 모든 수로 나누어보고 나머지가 0인 경우가 없으면 그보다 큰 수는 당연히 없다. 하지만 컴퓨터 입장에서는 제곱근 연산이 부담되므로 첫번째 방법이 나음. 세번째 방법. 에라토스테네스의 체 : 여러개의 수에 대해 소수 판별을 해야할 때 사용할 수 있다. 1. 1을 제외한 모든 수를 표에 적는다. 2. 현재 수가 지워져 있다면 다음 수로 이동. 3. 현재 수가 지워져 있지 않다.. 2020. 3. 10. 카테고리 정의 이 카테고리는 프로그래밍에 유용하거나 자주사용되는 수학적 내용들을 코드와 함께 정리하는 카테고리 2020. 3. 10. 이전 1 다음