소수(Prime Number)
약수가 1 그리고 자기 자신밖에 없는 수
- N이 소수가 되려면, 2보다 크거나 같고, N-1보다 작거나 같은 자연수로 나누어 떨어지면 안된다.
- 1부터 10까지의 소수 : 2, 3 ,5 ,7
소수 관련 알고리즘
- 어떤 수 N이 소수인지 아닌지 판별하는 방법
- N보다 작거나 같은 모든 자연수 중에서 소수를 찾아내는 방법
어떤 수 N이 소수인지 아닌지 판별하는 방법
1. N/2까지 확인하는 방법
- N이 소수가 되려면, 2보다 크거나 같고, N/2보다 작거나 같은 자연수로 나누어떨어지면 안된다.
- 이유 : N의 약수 중에서 가장 큰 것은 N/2보다 작거나 같기 때문이다.
- N = a * b로 나타낼 수 있는데, a가 작을수록 b는 크다.
- 가능한 a중에서 가장 작은 값이 2이기 때문에, b는 N/2를 넘지 않는다.
[N/2 값까지 나누어 떨어지는 확인하는 방법]
boolean prime(int n){
if(n < 2){
return false;
}
for (int i =2; i<=n/2; i++){
if(n %i == 0){
return false;
}
}
return true;
}2. √n까지 확인하는 방법
- N이 소수가 되려면, 2보다 크거나 같고, √n 보다 작거나 같은 자연수로 나누어 떨어지면 안된다.
- 이유 : N이 소수가 아니라면, N = a * b로 나타낼 수 있다. (a <= b)
- a > b라면 두 수를 바꿔 항상 a <= b로 만들 수 있다.
- 두 수 a와 b의 차이가 가장 작은 경우는 √n이다.
- 따라서 √n까지만 검사해보면 된다.
[ √n 값까지 나누어 떨어지는지 확인하는 방법]
boolean prime(int n){
if(n < 2){
return false;
}
for (int i =2; i*i<=n; i++){
// i*i는 √n의 범위를 정수의 표현으로 바꾸어 표현하기 위해 사용
// √같은 실수보다 정수로 표현해 코드를 작성하는것을 추천한다.
if(n %i == 0){
return false;
}
}
return true;
}- 컴퓨터에서 실수는 근사값을 나타내기 때문에, √n과 같은 경우는 위 코드처럼 정수의 표현으로 나타내는것이 좋다.
- ( √i <= N)은 (i <= N * N)과 같다.
- 어떤 수 N이 소수인지 아닌지 판별하는데 걸리는 시간: O(√n)
N보다 작거나 같은 모든 자연수 중에서 소수를 찾아내는 방법
위에서 사용한 방법으로 1부터 N까지 모든 소수를 구하는데 걸리는 시간복잡도는 O(N√N)이 걸린다. 따라서, 1부터 N까지 범위 안에 들어가는 모든 소수를 구하려면 에라토스테네스의 체라는 방법을 사용한다.
- 2부터 N까지 모든 수를 써놓는다.
- 아직 지워지지 않은 수 중에서 가장 작은수를 찾는다.
- 그 수는 소수이다.
- 이제 그 수의 배수를 모두 지운다.
[에라토스테네스의 체를 이용해 100이하의 모든 소수를 찾는 방법]
-
2의 배수인 빨간색으로 표시된 숫자를 모두 지운다.
-
3의 배수인 빨간색으로 표시된 숫자를 모두 지운다.
-
이렇게 2,3,5,7까지 배수를 모두 지우면 그 이후의 숫자들의 배수는 이미 지워져있기 때문에 더이상 수행할 필요가 없다. 즉, 남아있는 모든 수가 소수이다.
[에라토스테네스의 체 구현]
int prime[100]; // 소수 저장
int primeNumber = 0; // 소수의 개수
boolean checkPrimeNumber[101]; // 지워졌으면 true
int n = 100; // 100까지 소수
for (int i = 2; i <= n; i++) {
if (!checkPrimeNumber[i]) {
prime[primeNumber++] = i;
for (int j = i * i; j <= n; j += i) {
checkPrimeNumber[j] = true;
}
}
}- 1부터 N까지 모든 소수를 구하는것이 목표이기 때문에 바깥쪽
for문은 N까지 반복한다. - 안쪽
for문j는 N의 크기에 따라i * i또는i * 2로 바꾸는 것이 좋다. i가 백만일 경우i * i는 범위를 넘어가기 때문이다.
