✓

태그:

소수가 필요한 문제인데 왜일까요…??

풀이 비스무리한거 보기

주어진 범위의 자연수 중 2 이상의 제곱수로 나누어떨어지지 않는 자연수의 개수를 출력하는 문제입니다. 만약 1000001000000(max의 최댓값)보다 작거나 같은 제곱수를 다 구해서 주어진 범위의 자연수에 대해 모두 나누어 떨어지는지 체크하려고 했다면 그건 너무 오래 걸립니다. 그래서 고안한 방법은 아래와 같습니다.

1. 2부터 1000000까지 소수 판별
2. 각 소수에 대해
   1. min보다 크거나 같은 소수의 제곱의 배수 구하기
   2. 소수의 제곱만큼 더해가면서 범위에 해당하는 자연수는 제곱 ㄴㄴ 수라고 체크

굳이 소수를 판별한 이유는 합성수의 제곱은 소수의 제곱의 곱으로 표현할 수 있으므로 합성수의 제곱의 배수는 소수의 제곱의 배수이기 때문입니다. 이를 통해 불필요한 연산을 줄일 수 있습니다. 또한 범위의 각 수마다 제곱수로 나눈 나머지를 구하는 것보다는 각 제곱수에 대해 범위에 속하는 배수를 찾는게 훨씬 더 빠르기 때문에 이 방법을 채택했습니다.

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-02-01 23:09:37

---