프로그래머스 소수찾기

총 7자리이기 때문에 소수를 찾기 위해선 에라토스테네스의 체를 이용해야만 한다. NlgN만에 7자리까지 소수를 찾을 수 있기 때문이다. 그리고 순열과 완전탐색을 통해 모든 경우의 수를 찾은 후 정렬과 unique를 통해 중복을 삭제하도록 한다 

 

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

깃허브주소: https://github.com/surinoel/boj/blob/master/Programmers_소수찾기.cpp

 

	#include <vector>
	#include <string>
	#include <cstring>
	#include <algorithm>
	using namespace std;
	bool check[10000000];
	vector<int> totalset;
	void go(int cnt, int num, const vector<int> &idx) {
	if (cnt == idx.size()) {
	if (num != 0) {
	totalset.push_back(num);
	}
	return;
	}
	go(cnt + 1, num, idx);
	if (!(num == 0 && idx[cnt] == 0)) {
	go(cnt + 1, num * 10 + idx[cnt], idx);
	}
	return;
	}
	int solution(string numbers) {
	string s = numbers;
	vector<int> idx;
	for (int i = 0; i < s.size(); i++) {
	int num = s[i] - '0';
	idx.push_back(num);
	}
	sort(idx.begin(), idx.end());
	do {
	go(0, 0, idx);
	} while (next_permutation(idx.begin(), idx.end()));
	sort(totalset.begin(), totalset.end());
	totalset.erase(unique(totalset.begin(), totalset.end()), totalset.end());
	memset(check, true, sizeof(check));
	check[1] = false;
	for (int i = 2; i * i < 10000000; i++) {
	if (!check[i]) continue;
	for (int j = i + i; j < 10000000; j += i) {
	check[j] = false;
	}
	}
	int ans = 0;
	for (int i = 0; i < totalset.size(); i++) {
	if (check[totalset[i]]) {
	ans += 1;
	}
	}
	return ans;
	}

view raw Programmers_소수찾기.cpp hosted with ❤ by GitHub