Problem Solving
boj 1124 : 언더프라임
1ssrek
2016. 8. 26. 18:10
boj 1124 : 언더프라임
https://www.acmicpc.net/problem/1124
1이 아닌 소수 약수의 갯수를 구하면된다.
에라토스테레스의 체를 응용하여 구할 수 있다.
에라토스테레스의 체에서 바꾼건 i가 소수일 때 i가 j를 나눌 수 있으면 나눌 수 있을 만큼 나누고 나눴던 횟수를 a[j]에 누적한다.
"i가 소수인가?"는 "a[i]가 0인가?"와 동치이다.
그러면 a[a[i]]가 0이면 i는 언더프라임이다.