https://school.programmers.co.kr/learn/courses/30/lessons/42839
소수란
1과 자기 자신 이외의 자연수로는 나눌 수 없는 자연수
2,3,5,7,11.....
1은 소수가 아니다
2는 소수 중 유일한 짝수이다
n이 소수인지 확인하기
n이 소수이려면 1과 n자기 자신만이 약수여야 한다.
n이 1과 자기자신을 제외한 수로 나눠지면 소수가 아니고 나눠지지 않으면 소수이다.
2부터 n-1까지를 모두 순회하며 확인 할 수 있지만 이는 효율성이 떨어진다.
사실 제곱근 이하의 수만 n으로 나눠떨어지는지 판별해도 n이 소수인지 알 수 있다.
제곱근 이상의 수는 이미 제곱근 이전의 약수와 짝을 이루기 때문이다
만약 100의 약수를 찾을 때 약수들은 1, 2, 5, 10, 20, 50, 100이다.
이 때 제곱근인 10이상의 수는 1,2,5와 짝이 되므로 굳이 검사할 필요없다.
function isPrimeNum(n) {
if (!n || n === 1) return false;
for (let i = 2; i <= Math.sqrt(n); i++) {
if (n % i === 0) return false;
}
return true;
}
n보다 작거나 같은 소수 갯수 구하기
에라토스테네스의 체
소수를 찾은다음, 그 소수의 배수를 삭제하고 남은 수가 진정한 소수이다
2의 배수 삭제
3의 배수 삭제
5의 배수 삭제
...
function findPrimeCount(n) {
const isPrime = Array.from({ length: n + 1 }, () => true);
let answer = 0;
// 2부터 소수를 찾는다
for (let num = 2; num <= n; ++num) {
if (isPrime[num]) {
answer++; // 소수를 찾으면 소수갯수++
// 소수를 찾으면 소수의 모든 배수를 소수가 아님으로 변경한다
for (let multiple = num * 2; multiple <= n; multiple += num) {
isPrime[multiple] = false;
}
}
}
return answer;
}
풀이
문자를 조합한뒤 다음 dfs에 넣기전에 소수인지 검사
011 같이 같은 문자가 있을수 있으므로 set을 사용함 (전에 없던 소수이면 set에 저장)
전체코드
// 완전탐색 dfs
function solution(numbers) {
const set = new Set();
function dfs(prev, remain) {
// 더이상 남은 숫자가 없음 종료
if (!remain.length) {
return;
}
for (let i = 0; i < remain.length; i++) {
const newNum = Number(prev + remain[i]);
if (isPrime(newNum)) {
set.add(newNum); // 소수이면 저장
}
const newRemain = [...remain];
newRemain.splice(i, 1);
dfs(newNum, newRemain);
}
}
dfs("", numbers);
return set.size;
}
function isPrime(n) {
if (!n || n === 1) return false;
for (let i = 2; i <= Math.sqrt(n); i++) {
if (n % i === 0) return false;
}
return true;
}