boj 1124 : 언더프라임

boj 1124 : 언더프라임

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

1이 아닌 소수 약수의 갯수를 구하면된다.

에라토스테레스의 체를 응용하여 구할 수 있다.

에라토스테레스의 체에서 바꾼건 i가 소수일 때 i가 j를 나눌 수 있으면 나눌 수 있을 만큼 나누고 나눴던 횟수를 a[j]에 누적한다.

"i가 소수인가?"는 "a[i]가 0인가?"와 동치이다.

그러면 a[a[i]]가 0이면 i는 언더프라임이다.