"소수 (prime number)"의 두 판 사이의 차이

위키원
이동: 둘러보기, 검색
(판별)
42번째 줄: 42번째 줄:
 
*〈[https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98_(%EC%88%98%EB%A1%A0) 소수 (수론)]〉, 《위키백과》</ref>
 
*〈[https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98_(%EC%88%98%EB%A1%A0) 소수 (수론)]〉, 《위키백과》</ref>
 
* 수학방 공식 홈페이지 - https://mathbang.net/199
 
* 수학방 공식 홈페이지 - https://mathbang.net/199
 +
* 김동이, 〈[https://www.opentutorials.org/module/1544/9469 정수론]〉, 《오픈튜토리얼스》, 2015-04-09
  
 
==같이 보기==
 
==같이 보기==

2019년 8월 1일 (목) 10:04 판

소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수를 의미한다. 예를 들어, 자연수 2, 3, 5의 약수는 1과 자기 자신뿐이기 때문에 자연수 2, 3, 5는 소수라고 할 수 있다.

개요

특징

  • 소수는 1보다 큰 자연수이다. 즉, 1은 소수가 아니다.
  • 소수의 약수는 1과 자기 자신뿐이다. 즉, 소수의 약수는 2개뿐이며, 역도 성립한다.
  • 2는 소수이지만, 2를 제외한 모든 짝수는 2를 약수로 가지므로 소수가 아니다.
  • 2, 3을 제외한 모든 소수는 자연수 n에 대해 6n-1 혹은 6n+1 꼴이다. 역은 성립하지 않는다.

판별

  • 1은 소수가 아니다.
  • 2는 소수이다.
  • 2를 제외한 모든 짝수는 소수가 아니다.
  • 1과 자기 자신만이 약수이기 때문에 홀수는 2와 n-1사이에서 약수를 가지지 않는다.

위 과정을 코드로 표현

bool isPrime(int n)
{ //정수 n이 소수이면 true를 반환한다.
     //1은 소수가 아니다.
    if(n == 1) 
        return false;
     
     //짝수는 2이면 소수이다.
    if(n % 2 == 0)
        return (n==2);
         
    for(int i=3; i<n; i+=2)
    { //2 ~ n-1 범위의 홀수 약수가 있는지 검사한다.
         //약수가 있다면 소수가 아니다.
        if(n % i == 0)
            return false;
    }
     //약수가 발견되지 않았으므로 소수이다.
    return true;
}[1]


각주

  1. 김동이, 〈정수론〉, 《오픈튜토리얼스》, 2015-04-09

참고자료

같이 보기