알고리즘 스터디 6

https://programmers.co.kr/learn/courses/30/lessons/12921#

코딩테스트 연습 - 소수 찾기

 

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한 조건

• n은 2이상 1000000이하의 자연수입니다.

입출력 예

n	result
10	4
5	3

입출력 예 설명

입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

 

C++을 사용한 제 풀이입니다

#include <string>
#include <vector>

using namespace std;

vector<bool> t;

int solution(int n) {
    for (int a = 0; a <= n; ++a){
        t.push_back(true);
    }
    
    for (int b = 2; b <= n; ++b){
        int c = 2;
        if (t[b]){
            while(b * c <= n){
                t[b * c] = false;
                ++c;
            }
        }  
    }
    
    int count = 0;
    for (auto i : t){
        if (i){
            ++count;
        }
    }
    
    return count - 2;
}

처음에는 n까지 1씩 증가시키면서 소수를 나눠서 나눠 떨어지는지 찾았는데

n이 증가할수록 효율이 너무 떨어졌다..

그래서 반대로 2부터 배수들을 전부 지워나가는식으로 문제를 해결했더니 통과했다!

---

두번째 for문과 3번째 count부분을 합칠 수 있을것 같아서 합쳐봤다.

#include <string>
#include <vector>

using namespace std;

vector<bool> t;

int solution(int n) {
    int answer = 0;
    for (int a = 0; a <= n; ++a){
        t.push_back(true);
    }
    
    for (int b = 2; b <= n; ++b){
        if (t[b]){
            for (int c = 2; b * c <= n; ++c){
                t[b * c] = false;
            }           
            ++answer;
        }  
    }
    
    return answer;
}