소수 찾기

인트로

오늘은 정겨운 소수 찾기 문제를 풀어보았습니다.

---

문제

레벨1 : https://school.programmers.co.kr/learn/courses/30/lessons/12921

---

나의 풀이

첫 번째 풀이의 경우 효율성에서 시간 초과가 났습니다. 그러고 보니 백준에서도 이런 문제를 풀었는데 똑같은 상황을 겪었던 기억이 나네요.. 그때도 뭐 체 방법을 써야 된다고 했었는데 까먹었습니다. 그래서 로직을 찾아봤습니다.

function solution(n) {
	let cnt = 1;
	let flag = 1;
	for (let j = 3; j <= n; j++) {
		for (let i = 2; i <= Math.sqrt(j); i++) {
			if(j%i===0) {
				flag=0;
				break;
			}
		}
		flag&&cnt++;
		flag=1;
	}
	return cnt;
}

에라토스테네스의 체

였네요. 아무튼 소수 관련 문제 풀 때 가장 자주 사용되는 방법이라고 하니 다음부터는 절대 까먹지않겠다는 다짐..

알고리즘 자체는 간단합니다. 2부터 소수를 구하고자 하는 구간을 배열로 미리 만듭니다. 그리고 소수를 제외한 모든 배수를 지워버리면 됩니다.

에라토스테네스의 체

function solution(n) {
	let array = new Array(n+1).fill(1); 
	for (let i = 2; i**2 <= n; i++) {
		if(array[i]) {
			//배수는 소수가 아님
			for (let j = i**2; j <= n; j+=i) {
				array[j]=0;
			}
		}
	}
	return array.filter(el => el===1).length-2;
}

---

다른 풀이 참고

에라토스테네스의 체를 Set을 이용하여 푸신 분도 있더라구요. 신기해서 다시 풀어봤습니다.

function solution(n) {
	const s = new Set();
	for (let i = 1; i <= n; i+=2) {
		s.add(i);		//홀수만 추가
	}
	s.delete(1); //1은 소수X
	s.add(2); //2는 소수
	for (let i = 3; i <= Math.sqrt(n); i+=2) {
		if(s.has(i)) {
			for (let j = i**2; j <= n; j+=i) {
				s.delete(j);
			}
		}
	}
	return s.size;
}

---

다들 정말 다양한 방식으로 푸네요.. 끝이 없다.