#12921 소수 찾기

문제 정리

1~n 사이 소수의 개수 반환 (1은 소수 아님)

생각해보기

소수의 특징이 …뭐지? 다른 수로 안 나눠져야 하는건데…
하나하나 나눠지는지 확인 할 수는 없고…
해야되나?

소수 벡터를 하나 만들어서… 소수를 저장하기!
그리고 앞에서부터 시작.
우선 2로 나눠지는거 다 빼고 2를 소수 벡터에 저장. 후 erase
그리고 3으로 나눠지는거 다 빼고 3을 소수 벡터에 저장. 후 erase
그럼 이미 4는 없을거고 1이랑 그 다음에 바로 5가 있을거니까 소수 벡터에 저장하고 erase

이런 식으로 하면 될 듯…..?ㅠㅠ되나 우선 해보자

코드 쓰기

int solution(int n) {
    int answer = 0;
    vector<int> v; // 전체 벡터
    vector<int> prime;
    
    // 전체 벡터 만들기
    for(int i=1; i<=n; i++){
        v.push_back(i);
    }
    
    while (v.size() != 1){
        prime.push_back(v[1]);
        for(int i=1; i<v.size(); i++){
            if(v[i] % v[1] == 0){
                v.erase(v.begin() + i);
            }
        }
    }
    
    answer = prime.size() - 1;
    
    return answer;
}

역시 한 테케에서 시간초과…
1000000 백만개 원소 넣는 벡터 만드는 과정부터 오바인듯?

그러면 애초에 vector<int> prime = {2, 3, 5, 7}; 이렇게 내가 아는 소수 몇 개 넣어놓고
이걸로 나눠지면 벡터 만들때 삽입을 애초에 안 해주면 좀 나아질까?

int solution(int n) {
    int answer = 0;
    vector<int> v; // 전체 벡터
    vector<int> prime = {2, 3, 5, 7};
    
    for(int i=11; i<n; i++){
        if(i % 2 != 0 && i % 3 != 0 && i % 5 != 0 && i % 7 != 0) {
            v.push_back(i);
        }
    }
    
    while(v.size() != 1){
        for(int i=1; i<v.size(); i++){
            if(v[i] % v[1] == 0){
                v.erase(v.begin() + i);
            }
            prime.push_back(v[1]);
            v.erase(v.begin() + 1);
        }
    }
    
    answer = prime.size();
    
    return answer;
}

이러면 그냥 첨부터 시간초과 -.-;;

using namespace std;

int solution(int n) {
    int answer = 0;
    vector<int> v; // 전체 벡터
    
    // 전체 벡터 만들기
    for(int i=2; i<=n; i++){
        v.push_back(i);
    }
    
    while(v.size() > 0){
        for(int i=0; i<v.size(); i++){
            if(v[i] % v[0] == 0){
                v.erase(v.begin() + i);
            }
        }
        answer++;
    }
    
    return answer-1;
}

이렇게 하면 딱 하나 시간초과.. 효율성은 0점 ㅋㅋ
아무래도 v.size()만큼 하나하나 비교하는데서 시간초과가 뜨는 것 같은데…

내 풀이

#include <string>
#include <vector>
#include <cmath>

using namespace std;

int solution(int n) {
    int answer = 0;
    vector<bool> v(n+1, 0);
    
    for(int i=2; i<=n; i++){
        if(v[i]){
            continue;
        }
        
        for(int k=i+i; k<=n; k+=i){
            v[k] = 1;
        }
    }
    
    for(int i=2; i<=n; i++){
        if(!v[i]) answer++;
    }
    
    return answer;
}

결국 검색한 후 힌트 얻고 풀었다….

풀고 나서 알게된 것

bool 벡터를 쓰는게 의외로 자주 쓰이는 것 같다. 소수냐 아니냐만 판별하면 되는거니까…

그리고 (int k=i+i; k<=n; k+=i) 2, 4, 6, 8같이 해당 수의 배수들을 필요로 할 때
자주 써먹을 것 같은 for 조건문..!!! 기억해야겠다