Gidhub BE Developer

# [Programmers] 소수 찾기

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;
}
``````

## [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;
}
``````
• [STL] set을 사용한 풀이

## [3] Answer Code (21. 01. 30)

``````class Solution {
private String DEFAULT_NUMBER_BY_STRING_TYPE = "";
boolean[] isPrime = new boolean[10_000_000];
boolean[] isUsed = new boolean[10_000_000];
HashMap<Integer, Integer> map = new HashMap<>();

public int solution(String numbers) {
init(10_000_000);

char[] toCharArray = numbers.toCharArray();
recur(toCharArray, toCharArray.length, 0, DEFAULT_NUMBER_BY_STRING_TYPE);
return (int) map.keySet().stream().count();
}

private void recur(char[] toCharArray, int size, int idx, String numberByStringType) {
if (idx == size) {
if (DEFAULT_NUMBER_BY_STRING_TYPE.equals(numberByStringType)) {
return;
}

Integer numberByIntegerType = Integer.valueOf(numberByStringType);

if (numberByIntegerType == 0
|| numberByIntegerType == 1) {
return;
}

if (isPrime[numberByIntegerType]) {
map.put(numberByIntegerType, 1);
}
return;
}

for (int i = 0; i < size; i++) {
if (isUsed[i]) {
continue;
}
// Use
isUsed[i] = true;
recur(toCharArray, size, idx + 1, numberByStringType + toCharArray[i]);

// Not use
isUsed[i] = false;
recur(toCharArray, size, idx + 1, numberByStringType);
}
}

private void init(int n) {
Arrays.fill(isPrime, true);

for (int i = 4; i < n; i += 2) {
isPrime[i] = false;
}

for (int i = 3; i < Math.sqrt(n); i += 2) {
if (isPrime[i]) {
for (int j = 3; i * j < n; j += 2) {
isPrime[i * j] = false;
}
}
}
}
}
``````
• 소수를 미리 구해놓고

Recursive 하게 문제의 조건을 구한다.