9213 꽤 좋은 숫자

자기 자신을 제외한 약수의 합이 자기 자신이 되는 자연수를 완전수라고 한다.
이 때, a 이상 b 이하의 자연수중에 자기 자신을 제외한 약수의 합이 완전수와 c이하로 차이나는 수가 몇개인지 찾는 문제이다.

하나하나 약수를 구해서 비교해주면 TLE가 뜬다.
이를 해결하기 위해 에라토스테네스의 체를 응용한다.
우선 주어진 범위만큼 배열을 잡는다. 그 배열의 값은 각 인덱스의 자신을 제외한 약수의 합이다.

값을 정해주기 위한 방법은 i=1부터 범위까지 반복하면서
j= i * 2 부터 범위까지 i만큼 증가하면서 반복하고 j 위치의 배열에 i를 더해준다.

이렇게 하면 자기 자신은 제외하면서 약수들을 전부 더해줄 수 있게 된다.

배열을 다 구성하였으면 조건대로 비교해주면 된다.

소스