Prime Number, Composite Number   소수 (素數), 합성수

(2022-07-09)

소수 , 소수


1. 소수(素數) (Prime Number)  

  ㅇ 더이상 나누어지지 않는 수
     - 1과 자기자신 외 다른 수로는 나누어지지 않는, 1보다 큰 자연수(양의 정수)
        . 무한개의 소수가 있음
           .. 例) 2, 3, 5, 7, 11, 13, 17, 19, 21, 23, 29, 31, 37, 41, 43, 47, 53, ...

  ㅇ 소수의 주요 성질
     -  소수 p > 1 
     -  p의 양의 약수로는, 1 과 자기자신 p 뿐임 
     -  소수는 무수히 많이 존재함

     *  정수를 소수로 분해(소인수 분해)하는 것의 어려움 => 현대 암호기술의 핵심
        . (소인수 분해 : 정수를 소수들의 곱으로 표현하는 것)

  ㅇ 소수의 판정
     - 에라토스테라스의 체가 유명
        . (2부터 시작하여, 모든 정수배수를, 체로 걸러내는 방법)    ☞ 소수 판정 참조

  ㅇ 소수의 정리 (prime number theorem)
     - 자연수가 무한히 커질 때, 그 안에 들어 있는 소수의 개수를 근사적으로 밝히는 정리
     - 구체적으로, 자연수 x가 충분히 클 때, x 보다 작은 소수의 개수는, 약 x/ln(x) 
         
[# \lim_{x \to \infty} \frac{π(x)}{x/\ln(x)} = 1 #]
. π(x) : 자연수 x을 넘지 않는 소수의 개수 2. 합성수 (Composite Number) ㅇ 소수가 아닌 수 - 1과 자기 자신이 아닌 다른 양의 정수의 곱으로 나타낼 수 있는 양의 정수 . 즉, 합성수 c = a b - 그 약수를 3개 이상의 수 (1,자기자신,소수) 로써 표현 가능함 3. 자연수에서 소수,합성수 ㅇ `1` => 소수도 합성수도 아님 ㅇ `1` 보다 큰 모든 정수 => 소수이거나 합성수 ㅇ 모든 자연수의 표현 => 소수들의 거듭제곱 및 곱으로 표시 가능 - 例) 36 = 22 x 32, 120 = 23 x 3 x 5 등 ㅇ 소수는 무한히 많이 있음 4. [참고사항] ㅇ 두 정수공약수가 1 뿐일 때 ☞ 서로소 (Coprime,Relatively Prime)

소수,최대공약수
   1. 소수, 합성수   2. 최대공약수   3. 소인수 분해  


Copyrightⓒ written by 차재복 (Cha Jae Bok)               기술용어해설 후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"