Leet Code - 204. Count Primes(C++)

예제: Count Primes

문제
Count the number of prime numbers less than a non-negative number, n.

Example:

Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

풀이

주어진 숫자 n보다 작은 소수의 개수가 몇 개 있는지 반환하는 문제이다.
문제를 어렵게 만드는 요인은 바로 '제한속도' 이다.

필자는 다음과 같은 사실에 중점을 두어 풀었다.
1. 2를 제외한 짝수는 소수가 없다.
2. n의 소수를 검사할 때, sqrt(n) 이하인 홀수로 나눠지는지 본다.

전체적인 소스코드는 아래와 같다.

소스 코드

class Solution {
public:
	int countPrimes(int n) {
		int res = 0;
		if (n >= 3)
			res++;

		for (int i = 3; i < n; i += 2) {
			if (isPrime(i))
				res++;
		}

		return res;
	}

	bool isPrime(int n) {
		for (int i = 3; i <= sqrt(n); i += 2) {
			if (n % i == 0)
				return false;
		}

		return true;
	}
};

풀이 후기

나름 생각을 많이해서 풀어서 통과는 했지만, 다른 알고리즘에 비해 속도가 느렸다.
다른 사람들의 풀이를 보니 필자가 언급한 두 가지 사실에 기반하여 풀었지만, map을 사용하거나 필터링 조건을 추가하는 등 속도를 줄이기 위한 노력이 더 많이 들어가 있었다.
효율성이란 항목.. 참 알고리즘도 인생도 효율 챙기기가 쉽지 않다.