[프로그래머스] 소수 찾기

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42839

프로그래머스

 

풀이

CHECK PRIME///////////////////////////////////////////////

소수들을 에라스토테네스의 체로 확인하자

원리는 간단하다. 소수들의 배수들은 소수가 아니라고 저장하는 것이다.

 

2부터 시작하자.

2 -> 소수이다.

2의 배수 4,6,8,10,12,14,.....들은 소수가 아닐 것이다

3 -> 3은 소수이다

3의 배수 6,9,12,15,18....들은 소수가 아닐 것이다

4 -> 

4는 이미 2의 배수라서 notPrime[4]=1로 저장되어 있으므로 그냥 넘어간다

5 -> 5는 소수이다

notPrime[5]=0이기 때문이다

5의 배수 10,15,20,25,30...들은 소수가 아닐 것이다.

 

....이를 반복하면 된다.

 

 

CHECK NUMBERS//////////////////////////////////////////

next_permutation을 사용하면 문자열 혹은 vector등의 모든 조합을 확인할 수 있다.

모든 조합들의 부분들을 확인하며

notPrime에 저장된 소수인지 아닌지에 대한 여부에 따라 

unordered_set<int>primes에 넣어주면 된다.

(중복이 있으면 안되니 set에 넣어준다)

 

마지막에 set의 size를 반환하면 끝

 

코드

#include <string>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <unordered_set>
#include <vector>
using namespace std;


int solution(string numbers) 
{
    unordered_set<int>primes;
    sort(numbers.begin(),numbers.end());
    
    //CHECK PRIME/////////////////////////////////
    vector<int>notPrime(10000000,0);
    notPrime[0]=1; notPrime[1]=1;
    for(int i=2;i<notPrime.size();i++)
    {
        if(notPrime[i]==1)continue;
        for(int k=i+i;k< notPrime.size();k+=i)
        {notPrime[k]=1;}
    }
    
    //CHECK NUMBERS///////////////////////////////
    do
    {
        string s="";
        for(int i=0;i<numbers.size();i++)
        {
            s+=numbers[i];
            if(!notPrime[stoi(s)]){primes.insert(stoi(s));}
        }
    }while(next_permutation(numbers.begin(),numbers.end()));
        
    return primes.size();
}