- PPT 내용을 포스팅으로 옮김.
에라토스테네스
고대 그리스의 수학자, 천문학자
[업적]
- 지구의 크기 계산
- 지축의 기울기 계산
- 달의 상대적 크기 계산
- 에라토스테네스의 체
소수를 구하는 방법
첫 번째 방법: O(N)
소수: 1보다 큰 자연수 중 1과 그 수 자기 자신만을 약수로 갖는 자연수
합성수: 1보다 크고 자기 자신의 수보다 작은 자연수를 약수로 갖게 되는 자연수
→ N보다 작은 자연수들로 모두 나눠서 나머지가 0이 나오는 값이 존재하면 합성수, 그렇지 않으면 소수
[코드]
public static void is_prime(int num) throws IOException {
// 0과 1의 경우 소수가 아님.
if (num < 2) {
bw.write("소수가 아닙니다.");
return;
}
// 2의 경우는 소수임.
if (num == 2) {
bw.write("소수입니다.");
return;
}
// 약수가 하나라도 존재한다면 소수가 아님.
for (int i = 2; i < num; i++) {
if (num % i == 0) {
bw.write("소수가 아닙니다.");
return;
}
}
bw.write("소수입니다.");
}시간 복잡도: 모든 수를 조사하기 때문에 O(N)
두 번째 방법: O(√N)
약수는 순서쌍으로 구성되어 있기 때문에 √N만큼만 반복해도 됨.
EX) 24의 약수 → 1 2 3 4 6 8 12 24
(1, 24) (2, 12) (3, 8) (4, 6) → 순서쌍의 마지막 원소의 첫 번째는 √N을 넘지 않음.
[코드]
public static void is_prime(int num) throws IOException {
// 0과 1의 경우 소수가 아님.
if (num < 2) {
bw.write("소수가 아닙니다.");
return;
}
// 2의 경우는 소수임.
if (num == 2) {
bw.write("소수입니다.");
return;
}
// 약수가 하나라도 존재한다면 소수가 아님.
for (int i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0) {
bw.write("소수가 아닙니다.");
return;
}
}
bw.write("소수입니다.");
}첫 번째 방법의 코드에서 i < num을 i <= Math.sqrt(num)으로 변경함.
시간 복잡도: √N까지만 조사하기 때문에 O(√N)
세 번째 방법: 에라토스테네스의 체 : O(Nlog(logN))
2부터 √N까지 반복하여 나오는 자연수들 중 본인을 제외한 배수들을 제외시키자.
EX) 2의 배수라는 뜻은 약수로 2를 가지고 있다는 뜻이며 2인 본인을 제외한 모든 수는 약수가 될 수 없음. 3의 배수도 마찬가지임.
4의 배수는 곧 2의 배수이며 굳이 검사할 필요가 없으니 넘어감.
2의 배수: 2를 제외한 모든 2의 배수 제외
3의 배수: 3을 제외한 모든 3의 배수 제외
…
√N의 배수: √N을 제외한 모든 √N의 배수 제외
[코드]
// true: 소수 X | false: 소수 O
public static void is_prime(int num) {
prime = new boolean[num + 1]; // 0 ~ N
if (num < 2) return;
// 2 미만의 N을 입력받으면 소수는 판별할 필요 없으므로 바로 반환
prime[0] = prime[1] = true; // 0과 1은 소수 처리 X
for (int i = 2; i <= Math.sqrt(num); i++) {
if (prime[i] == true) continue;
// 소수가 아님이 확정됐으면 패스
for (int j = i * i; j < prime.length; j = j + i) {
prime[i] = true;
}
}
}시간 복잡도: O(Nlog(logN))
에라토스테네스의 체 방식으로 문제 풀기
문제 설명
약수의 개수가 세 개 이상인 수를 합성수라고 합니다. 자연수 n이 매개변수로 주어질 때 n이하의 합성수의 개수를 return하도록 solution 함수를 완성해주세요.
제한사항
- 1 ≤
n≤ 100
입출력 예
| n | result |
|---|---|
| 10 | 5 |
| 15 | 8 |
입출력 예 설명
입출력 예 #1
- 10 이하 합성수는 4, 6, 8, 9, 10 로 5개입니다. 따라서 5를 return합니다.
입출력 예 #1
- 15 이하 합성수는 4, 6, 8, 9, 10, 12, 14, 15 로 8개입니다. 따라서 8을 return합니다.
class Solution {
public boolean[] prime;
public int solution(int n) {
int answer = 0;
is_composite(n);
for (int i = 1; i < n; i++) {
if (prime[i]) answer++;
}
return answer;
}
public void is_composite(int num) {
prime = new boolean[num+1];
if (num < 2) return;
prime[0] = prime[1] = true;
for (int i = 2; i <= Math.sqrt(num); i++) {
if (prime[i] == true) continue;
for (int j = i * i; j < prime.length; j = j + i) {
prime[j] = true;
}
}
}
}참고 자료
