위키원
"소수 (prime number)"의 두 판 사이의 차이
| 17번째 줄: | 17번째 줄: | ||
위 과정을 코드로 표현 | 위 과정을 코드로 표현 | ||
bool isPrime(int n) | bool isPrime(int n) | ||
| − | {//정수 n이 소수이면 true를 반환한다. | + | {''<font color=green>// 정수 n이 소수이면 true를 반환한다.</font>'' |
| − | //1은 소수가 아니다 | + | ''<font color=green>// 1은 소수가 아니다.</font>'' |
| − | if(n == 1) | + | <font color=#006699>if</font>(n == 1) |
| − | return false; | + | <font color=#006699>return false</font>; |
| − | //짝수는 2이면 소수이다. | + | ''<font color=green>// 짝수는 2이면 소수이다.</font>'' |
| − | if(n % 2 == 0) | + | <font color=#006699>if</font>(n % 2 == 0) |
| − | return (n==2); | + | <font color=#006699>return</font> (n==2); |
| − | for(int i=3; i<n; i+=2) | + | <font color=#006699>for</font>(int i=3; i<n; i+=2) |
| − | {// 2 ~ n-1 범위의 홀수 약수가 있는지 검사한다. | + | {''<font color=green>// 2 ~ n-1 범위의 홀수 약수가 있는지 검사한다.</font>'' |
| − | //약수가 있다면 소수가 아니다. | + | ''<font color=green>// 약수가 있다면 소수가 아니다.</font>'' |
| − | if(n % i == 0) | + | <font color=#006699>if</font>(n % i == 0) |
| − | return false; | + | <font color=#006699>return false</font>; |
} | } | ||
| − | //약수가 발견되지 않았으므로 소수이다. | + | ''<font color=green>// 약수가 발견되지 않았으므로 소수이다.</font>'' |
| − | return true; | + | <font color=#006699>return true</font>; |
} | } | ||
2019년 8월 1일 (목) 09:59 판
소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 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;
}
각주
참고자료
- 〈소수 (수론)〉, 《위키백과》</ref>
- 수학방 공식 홈페이지 - https://mathbang.net/199
