숫자 n 까지의 소수를 찾는 문제이다. 처음에는 n까지 for 문을 돌면서 소수를 판별하는 함수로 개수를 세려고 했는데 이렇게 해보니
효율성 테스트에서 시간초과가 떴다. 왜 그런지 생각해보니 for문을 돌면서 계속 검사를 하면 O(N^2)로 시간복잡도가 계산되기 때문에 실패하는 것이였다.
방법을 찾아보니 에라토스테네스의 체 라는 방법을 사용하면 시간을 많이 줄일 수 있다고 해서 이 방법을 익히고 사용해 보기로 하였다.
에라토스테네스의 체
에라토스테네스의 체를 설명한 그림이다.
소수 인것을 찾고 소수의 배수를 찾아 체크하는 과정을 반복하면 체크하지 않은 것이 소수이여서 이런 방식으로 소수를 찾을 수 있다.
전체 코드
#include <string>
#include <vector>
using namespace std;
int solution(int n) {
int answer = 0;
vector<bool> v(n+1,true);
for(int i=2;i<=n;i++){ //전체 순회
if(v[i]){ //소수라면
for(int j=2;j*i<=n;j++){ //배수 찾기
v[i*j]=false; //배수는 소수가 아니다.
}
answer++;
}
}
return answer;
}
'코딩테스트 > 프로그래머스' 카테고리의 다른 글
[프로그래머스][LV 1][C++] [1차] 다트 게임 (2) | 2024.03.05 |
---|---|
[프로그래머스][LV 1][C++] 실패율 (0) | 2024.03.04 |
[프로그래머스][LV 1][C++] 소수 만들기 (0) | 2024.03.01 |
[프로그래머스][LV 1][C++] 2016년 (0) | 2024.02.29 |
[프로그래머스][LV 1][C++] [1차] 비밀지 (0) | 2024.02.29 |