프로그래머스 : 소수 찾기

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42839

프로그래머스

 

 

 문제 설명 

 

숫자로 이루어진 문자열이 주어지면 그숫자들로 만들 수있는 소수 의 갯수를 return 하는것.

 

 알고리즘 

 

1 . 주어진 문자열로 만들수 있는 숫자들을 재귀함수로 만든다.

    -문자열을 int 형으로 바꾸어주는 stoi("string") 함수를 이용 

 

2. 만든 숫자들이 소수 인지 판별하는 함수를 만든다.

    - 에라토스테네스의 체 이용 .

    - n이 소수임을 판별하기 위해 2부터 sqrt(n) 까지 나누어 떨어지는지 확인 하면되기에 효율적.

 

3. 소수면 cnt++ 한다.

 

 

 코드 

 

#include <string>
#include <vector>
#include<iostream>
#include<math.h>
using namespace std;
int answer = 0;
int Size;
string a;
int arr[9999999] = { 0, };
int pri[9999999] = { 0, };
int idx_check[8];
bool prime(int n) { //소수구하기
    if (n < 2)return false;
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0)return false;
    }
    return true;
}
 
 
void check(int n,string str) { //숫자 만들기 
    if (str.length() == n) {
        if (prime(stoi(str))) { //stoi 함수 이용 .
            if (!arr[stoi(str)]) {
                answer++;
                arr[stoi(str)] = 1;
 
            }
        }
        return;
    }
    for (int i = 0; i < Size; i++) {
        if (idx_check[i])continue;
        idx_check[i] = 1;
        check(n, str + a[i]);
        idx_check[i] = 0;
    }
 
 
}
 
 
int solution(string numbers) {
 
    Size = numbers.size();
    a = numbers;
 
    for (int i = 1; i <= Size; i++) {
        check(i, "");
    }
    return answer;
}