Programmers / 소수 찾기 / C++

*문제 출처는 프로그래머스에 있습니다.

 

문제 제목: 소수 찾기 (1단계)

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/120817

프로그래머스

 

문제 설명

 

---

 

나의 풀이

 

1차 시도

#include <string>
#include <vector>
#include <cmath>
using namespace std;

bool prime(int num) {
    for (int i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) return false;
    }
    return true;
}

int solution(int n) {
    int answer = 0;
    vector<int> number;
    
    for (int i = 2; i <= n; i++) 
        if (prime(i) == true) number.push_back(i);
    
    answer = number.size();
    
    return answer;
}

 

이상하게 효율성 검사에서 시간초과가 뜬다. 이렇게 풀면 시간 복잡도는 O(√n)이라서 당연하게 풀릴 줄 알았다.

문제를 다시 보니깐 소수의 개수를 반환해라고 나와있다. 아마 하나씩 소수를 찾는다고 효율성에서 초과된 것 같다.

 

2차 풀이

#include <string>
#include <vector>
#include <cmath>
using namespace std;

int solution(int n) {
    int answer = 0;
    vector<bool> isPrime(n + 1, true);
    vector<int> number;
    
    for (int i = 2; i <= n; i++) {
		if (isPrime[i]) {
			number.push_back(i);
			for (int j = i * 2; j <= n; j += i) {
				isPrime[j] = false;
			}
		}
	}
    answer = number.size();
    
    return answer;
}

 

이번에는 에라토스테네스의 체 알고리즘 을 빌려와서 사용했다. O(N * log log N)의 시간복잡도를 가진다고한다.

---

※ 알아야 할 것

 

에라토스테네스의 체 알고리즘을 알아야 쉽게 풀 수 있던 것 같다.