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

(2019-05-23)

소수, 소수

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부터 시작하여, 모든 정수배수를 체로 거르는 방법)가 유명

  ㅇ 소수 판정에 대한 간단한 코딩 구현 例)
     - (C 언어)
        
int is_prime (int n) {
    int i;
    if (n < 2) return 0;
    for (i = 2; i*i < n; i++) {  // i < n or i < n/2 or i*i < n
        if (n % i == 0) return 0;
    }
    return i;
}
- (자바 언어)
public static boolean isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i*i < n; i++)  // i < n or i < n/2 or i*i < n
        if (n % i == 0) return false;
    return true;
}
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. 소인수 분해

 
        최근수정     요약목록     참고문헌