문제 요약
자세한 내용은 leetcode에서 확인
https://leetcode.com/problems/count-primes/
0부터 n까지 몇개의 소수가 있을까?
풀이
이거슨 바로 수학 문제다. 공식을 모르면 풀 수 없으니 무조건 외운다.
먼저 소수의 정의와 팩트들을 먼저 알아야 한다.
- 자기자신과 1로만 나누어 지는 수
- 0과 1은 소수가 아니다
- 소수 중에 짝수는 2가 유일하다
이 문제는 Sieve by Eratosthenes algorithm을 알아야만 풀 수 있다. 알고리즘 설명은 유투브에 많으니 개념설명은 넘어가고 구현된 코드를 본다.
public int countPrimes(int n) {
boolean prime[] = new boolean[n+1];
// 배열 기본값을 true로 세팅해준다
for (int i = 0; i< n; i++) {
prime[i] = true;
}
// outer loop은 i*i < n 만큼 돈다
// 0과 1은 소수가 아니기 때문에 2부터 시작한다
// 예로 n=10일 경우, i는 2부터 3까지 간다
for (int i = 2; i*i < n; i++) {
if (prime[i]) {
// inner loop은 i의 다음 배수부터 시작한다
// i의 배수는 소수가 아니기 때문에 마킹한다
for (int j = i*i; j < n; j += i)
prime[j] = false;
}
}
int count = 0;
// 소수 카운팅
for (int i = 2; i < n; i++) {
if (prime[i])
count++;
}
return count;
}
Complexity
time: O(n*log(log(n)))
space: O(1)