Gidhub BE Developer

[Programmers] 42839. 소수 찾기

2018-09-26
goodGid

Problem

Problem URL : 소수 찾기


[1] Answer Code (18. 09. 26)

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

bool p[10000000]; // p is Prime Number
bool c[10000000];

int solution(string s) {
    memset(p,1,sizeof(p));
    p[0] = false;
    p[1] = false;
    for(int i=2; i*i<10000000; i++){
        if(p[i] == false) continue;
        p[i] = true;
        for(int j=i*2; j<10000000; j+=i)
            p[j] = false;
    }
    
    int ans=0;
    int size = (int)s.size();
    sort(s.begin(),s.end());
    do{
        for(int i=1; i<=size; i++){
            int n;
            n = stoi(s.substr(0,i));
            if(!c[n] && p[n]){
                c[n] = true; // n값은 사용했다.
                ans++;
            }
        }
    } while(next_permutation(s.begin(),s.end()));
    return ans;
}

Review


[2] Answer Code (18. 09. 26)

#include <iostream>
#include <cstring>
#include <set>
#include <algorithm>
using namespace std;

bool p[10000000]; // p is Prime Number

int solution(string s) {
    memset(p,1,sizeof(p));
    p[0] = false;
    p[1] = false;
    for(int i=2; i*i<10000000; i++){
        if(p[i] == false) continue;
        p[i] = true;
        for(int j=i*2; j<10000000; j+=i)
            p[j] = false;
    }
    
    set<int> se;
    int ans=0;
    int size = (int)s.size();
    sort(s.begin(),s.end());
    set<int>::iterator iter;
    
    do{
        for(int i=1; i<=size; i++){
            int n;
            n = stoi(s.substr(0,i));
            iter = se.find(n);
            if(iter == se.end() && p[n]){
                se.insert(n);
                ans++;
            }
        }
    } while(next_permutation(s.begin(),s.end()));
    return ans;
}

Review

  • [STL] set을 사용한 풀이

Comments

Content