소수 구하기의 시간 복잡도 줄이기 알고리즘(에라토스테네스의 체)
문제 링크
가장 처음 코드 - 기본적인 접근
function solution(num) {
const START = 2; // 소수는 2부터 시작하기 때문에 start를 2로 지정
let isPrime; // i%j===0 이면 소수이기 때문에 check를 1로 바꿔주어 sum+=1을 하지 않게 한다.
let sum = 0;
// 1. 이중 for문 만들기 (i : 2부터 num까지 반복 , j : 2부터 num까지 반복 )
for ( let i = START; i <= num; i++) {
isPrime = true;
for (let j = START; j < i - 1; j++) {
// 2. 만약(if) i%j == 0 이라면 소수가 아니므로 패스. j를 다 돌았는데 i%j==0인게 없으면 소수이므로 sum+=1
if (i % j === 0) {
isPrime = false;
}
}
if (isPrime) {
sum += 1;
}
}
return sum;
}
→ 필요 없는 반복이 잦아져서 큰 값을 넣으면 시간 초과로 실행이 안 된다.
첫 번째 생각 : 짝수만 비교하자!
생각하게 된 계기
- 2를 제외한 짝수는 모두 소수가 아니기 때문에 굳이 비교할 필요가 없다.
의사 코드
- i = 2인 경우를 예외처리를 해주고 i+=2를 해주면 된다.
코딩
바꾼 부분은 빨간펜 표시를 했다. (캡처 전 미처 바꾸지 못한 부분은 노란색으로 타이핑)
const START = 3 → 3부터 해서 홀수만 비교를 하므로 START를 3으로 바꾸어주었다.
- 주석을 다시 바꾸었다.
let sum = 1; → 2는 비교를 하지 않기 때문에 sum을 값 2를 포함한 1부터 시작한다.
if(num == 2) → num이 2인 경우에 예외처리를 위해 써주었다.
- ==를 ===로 고쳤다.
i+=2 → 홀수만 비교하기 위해 2씩 더해주었다.
<정확성 테스트>
테스트 1 〉통과 (1.71ms, 37.3MB)
테스트 2 〉통과 (1.87ms, 37.1MB)
테스트 3 〉통과 (3.09ms, 37MB)
테스트 4 〉통과 (3.75ms, 37MB)
테스트 5 〉통과 (3.30ms, 36.9MB)
테스트 6 〉통과 (63.58ms, 37.5MB)
테스트 7 〉통과 (8.09ms, 36.8MB)
테스트 8 〉통과 (34.49ms, 36.9MB)
테스트 9 〉통과 (86.13ms, 37.1MB)
테스트 10 〉실패 (시간 초과)
테스트 11 〉실패 (시간 초과)
테스트 12 〉실패 (시간 초과)<효율성 테스트>
테스트 1 〉실패 (시간 초과)
테스트 2 〉실패 (시간 초과)
테스트 3 〉실패 (시간 초과)
테스트 4 〉실패 (시간 초과)
→ 전보다 시간이 2배로 줄었지만 그래도 큰 값을 받으면 시간 초과가 된다.
두 번째 생각 : 반만 비교하자!
생각하게 된 계기
j를 끝까지 돌릴 필요가 있을까?
어차피 j를 반만 돌려도 소수라는 것이 증명되기 때문에 끝까지 돌릴 필요가 없을 것 같다.
의사 코드
- j를 반만 돌린다. for j의 조건식을 고치자
코딩
j<(i-1)/2 → j를 반까지만 돌리면 되기 때문에 /2를 했다.
<정확성 테스트>
테스트 1 〉통과 (1.74ms, 36.7MB)
테스트 2 〉통과 (1.77ms, 37.1MB)
테스트 3 〉통과 (3.10ms, 36.7MB)
테스트 4 〉통과 (3.43ms, 36.7MB)
테스트 5 〉통과 (3.16ms, 37MB)
테스트 6 〉통과 (33.53ms, 36.7MB)
테스트 7 〉통과 (5.68ms, 36.6MB)
테스트 8 〉통과 (18.90ms, 37.3MB)
테스트 9 〉통과 (44.78ms, 37MB)
테스트 10 〉실패 (시간 초과)
테스트 11 〉실패 (시간 초과)
테스트 12 〉실패 (시간 초과)<효율성 테스트>
테스트 1 〉실패 (시간 초과)
테스트 2 〉실패 (시간 초과)
테스트 3 〉실패 (시간 초과)
테스트 4 〉실패 (시간 초과)
→ 시간이 또 반으로 줄었지만, 여전히 큰 수는 받지 못한다.
세 번째 생각 : 에라토스테네스의 체
생각하게 된 계기
- 지인이 힌트를 주었다.
개념
- 에라토스테네스의 체는 배열에 모든 수를 넣고 2부터 검사하는데, 2를 넣으면 2의 배수들은 다 지우고, 그다음 3을 넣으면 3은 다 지우고 … 이런 식으로 반복하는 알고리즘이다.
의사 코드
- 배열을 하나 선언해서 num까지 수를 모두 넣어 놓는다.
- 비교 수가 true라면 비교 수의 배수를 모두 false로 바꾼 후 sum++를 해준다.
- false 값이 있는 배열은 비교하지 않는다.
코딩
대공사를 거쳤다… 거의 모든 부분이 바뀌어서 빨간펜을 하나하나 칠 수 없었다. ^_ㅠ
const START = 2 → 배수를 지우는 방법이기 때문에 소수는 다시 2부터 시작하게 했다.
let sum = 0 → 그래서 sum도 다시 0으로 바꾸었다.
let all_num = []; → 모든 수를 넣어줄 배열을 만들었다.
for(let i = 0; i< num; i++) → 모든 수를 넣어줄 for문을 만들었다.
for(let i=START; i≤num; i++) → 2부터 끝까지 도는 for문을 만들었다. (전체를 돌 for문)
if(all_num[i] === 0) → 0(검색 제외 대상)이면 아래 문장을 실행하지 않고 위로 올라가게 continue를 사용했다.
for(let j = i*2; j≤num; j+=i) → i의 배수를 지워주는 과정이다.
all_num[j] = 0 → 검색 제외 대상으로 만들기 위해 0을 넣었다.
sum++ → 끝까지 실행되면 1을 누적해준다.
<정확성 테스트>
테스트 1 〉통과 (1.67ms, 36.6MB)
테스트 2 〉통과 (1.70ms, 41MB)
테스트 3 〉통과 (1.85ms, 37.3MB)
테스트 4 〉통과 (1.79ms, 37.3MB)
테스트 5 〉통과 (1.74ms, 37MB)
테스트 6 〉통과 (3.56ms, 37.5MB)
테스트 7 〉통과 (1.94ms, 37MB)
테스트 8 〉통과 (2.33ms, 37.2MB)
테스트 9 〉통과 (3.58ms, 37.5MB)
테스트 10 〉통과 (14.07ms, 46.3MB)
테스트 11 〉통과 (172.17ms, 67MB)
테스트 12 〉통과 (39.08ms, 45.9MB)<효율성 테스트>
테스트 1 〉통과 (141.06ms, 66.8MB)
테스트 2 〉통과 (31.30ms, 66.9MB)
테스트 3 〉통과 (92.51ms, 66.9MB)
테스트 4 〉통과 (131.74ms, 67.6MB)
→ 시간도 대폭 줄었고(아마 반복 횟수가 확실히 많이 줄어서 그런 것 같다) 정확성, 효율성 테스트를 모두 통과하였다.
최종 코드
function solution(num) {
const START = 2; // 소수는 2부터 시작하기 때문에 start를 2로 지정
let sum = 0;
let all_num = [];
for (let i = 0; i < num; i++) { // 모든 수를 넣어준다
all_num[i] = i;
}
for (let i = START; i <= num; i++) {
if (all_num[i] === 0) {
continue;
}
for (let j = i * 2; j <= num; j += i) {
all_num[j] = 0; // 검색 대상에서 제외
}
sum++;
}
return sum;
}참고 문헌
에라토스테네스의 체