소수 찾기

• 소수와 관련된 문제시 사용할 수 있는 것들
  1) 숫자 n이 소수인지 판별 (isPrime)

bool isPrime(int n){
  if(n < 2) return false;
  /* 특정 수가 소수인지 판별할 때 그 수의 제곱근까지만 판별하면 된다! */
  for(int i=2;i<= sqrt(n);i++)
  	if(n % i == 0) return false;
  return true;
}

2) 1~n까지 소수 판별 (에라토스테네스의 채)

int N="1024";
vector<bool> v(N+1, true);

for(int i=2;i<=N;i++)
{
  if(v[i] == false) continue;
  for(int j=2; i*j <= N; j++) v[i*j] = false;
}

코드

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

int solution(string numbers) {
    int answer = 0;
    // 1) numbers를 문자열로 변환한 뒤 내림차순 정렬 (내림차순 정렬한 수 = 최대 나올 수 있는 수)
    sort(numbers.begin(), numbers.end(), greater<char>());
    int N = stoi(numbers);
    vector<bool> num(10000002, true);
    num[0] = false; num[1] = false;
    // 2) 소수 여부 저장
    for(int i=2;i<=N;i++)
    {
        if(num[i] == false) continue;
        for(int j=2;i*j<=N;j++) num[i*j] = false;
    }
    // 3) 2~해당 숫자 사이에 있는 소수가 내가 가진 값들로 만들 수 있는지 검사 & count! 
    for(int i=2;i<=N;i++)
    {
        int flag=0;
        string str = numbers;
        string s_sosu = to_string(i);
        if(num[i] == false) continue;
        for(int j=0;j<s_sosu.length();j++)
        {
            int tmp = 0;
            for(int k=0;k<str.length();k++)
            {
                if(s_sosu[j] == str[k])
                {
                    /* 해당 문자가 있다면 중복사용 안되게 공백 처리 */
                    str[k] = ' ';
                    tmp = 1;
                    break;
                }
            }
            /* str에서 내가 원하는 값이 없을 때 */
            if(tmp == 0) {
                flag =1;
                break;
            }
        }
        if(flag == 0){
            answer++;
        }
    }
    return answer;
}

• 로직
  1) 수의 최대 범위 구하기
      : numbers를 내림차순 정렬한 뒤 stoi()로 바꾸어 최대 숫자 크기를 구함
  2) 최대 숫자 이하의 소수를 판별하는 '에라토스테네스의 채' 배열 구하기
  3) 2~최대숫자 중 소수이면서 && 내가 가진 문자로 표현 가능한 것들 count!