Baekjoon 1124번 언더프라임

문제

https://www.acmicpc.net/problem/1124

걸린 시간

-

풀이

TypeScript

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input';
const stdin = fs.readFileSync(filePath).toString().trim().split('\n').map((s: string) => s.trim());
const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

const [a, b] = input().split(' ').map(Number);

const MAX_SIZE: number = 100001;
const dp: number[] = Array(MAX_SIZE).fill(0);
const prime: number[] = []; // 소수 목록
const isPrime: boolean[] = Array(MAX_SIZE).fill(true); // 에라토스테네스
isPrime[0] = isPrime[1] = false;

for(let i = 2; i < MAX_SIZE; i++){
  if(!isPrime[i]) continue;
  prime.push(i);
  dp[i] = 1;
  for(let j = i+i; j < MAX_SIZE; j += i){
    isPrime[j] = false;
  }
}

for(let i = 4; i < MAX_SIZE; i++){
  if(isPrime[i]) continue;
  let j: number = 0;
  while(j < prime.length && i%prime[j] !== 0){
    j++;
  }
  dp[i] = dp[prime[j]] + dp[i/prime[j]];
}

let ans: number = 0;
for(let i = a; i <= b; i++){
  if(isPrime[dp[i]]) ans++;
}
console.log(ans);

에라토스테네스의 체 + dp 를 이용한 풀이

예제를 몇개 풀어보니 소인수의 개수를 tabulation 할 수 있겠단 생각이 들었다. 에라토스테네스의 체를 이용하여 소수 목록을 전부 구해두고, 소수가 아닌 것들에 대해서만 첫 번째 소인수를 찾고 나머지는 dp 배열에서 가져다 사용했다.

점화식 : dp[i] = dp[prime[j]] + dp[1/prime[j]]

dp[i] = 1 + dp[1/prime[j]] 와도 같겟다.