소수와 소인수분해
소수(prime number)
소수(prime number)란 1과 자기 자신으로밖에 나누어지지 않는 1보다 큰 자연수를 의미합니다.
즉, 소수는 1과 자기 자신, 단 두 개의 약수만을 가집니다.
소수 예제) 2, 3, 5, 7, 11, 13, 17, 19, 23, ...
단, 1은 소수가 아니며, 2는 유일한 짝수인 소수입니다.
소수와 소인수분해에 대한 더욱 자세한 내용은 중학교 1학년 수학 과목에서 배우실 수 있습니다.
소수와 소인수분해는 보안과 관련된 암호문 작성 및 암호 프로그램을 처리하는 데 많이 사용됩니다.
합성수(composite number)
합성수(composite number)란 1과 자기 자신 이외의 또 다른 수를 약수로 가지는 자연수를 의미합니다.
즉, 합성수는 1과 자기 자신 외에 또 다른 약수를 가지므로 언제나 세 개 이상의 약수를 가집니다.
합성수 예제) 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, ...
단, 1은 소수도 아니고 합성수도 아니며, 1보다 큰 모든 자연수는 소수이거나 합성수이다.
소인수분해(prime factorization)
소인수분해(prime factorization)란 합성수를 소수들의 곱으로만 나타내는 것을 의미합니다.
합성수를 소인수분해한 결과는 소인수들의 순서를 생각하지 않으면 오직 한 가지 형태만이 존재합니다.
예제) 12를 소인수분해하시오.
12의 인수 = {1, 2, 3, 4, 6, 12} → 12의 소인수 = {2, 3} → 12 = 22 × 31
∴ 22 × 31
소인수란 해당 합성수의 인수 중 소수들을 가리킵니다.
소인수분해 방법
소인수분해를 하는 가장 간단한 방법은 다음과 같습니다.
1. 해당 합성수를 소인수로 몫이 소수가 될 때까지 나눗셈을 계속합니다.
2. 사용된 모든 소인수와 마지막 몫을 지수의 형태로 곱합니다.
예제) 72를 소인수분해하시오.
∴ 72 = 23 × 32
