[백준 1016] 파이썬(Python) 제곱ㄴㄴ수 - 에라토스테네스의 체

제곱 ㄴㄴ 수

어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수가 몇 개 있는지 출력한다.

입력

첫째 줄에 두 정수 min과 max가 주어진다.

출력

첫째 줄에 min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수의 개수를 출력한다.

제한

• 1 ≤ min ≤ 1,000,000,000,000
• min ≤ max ≤ min + 1,000,000

예제 입력 1

1 10

예제 출력 1

7

---

에라토스테네스의 체 알고리즘

에라토스테네스의 체는 소수를 찾는 방법 중 하나입니다.

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열합니다.
2. 2 자신을 제외한 2의 배수를 모두 지웁니다.
3. 남아있는 수 가운데 3은 소수이므로 놔두고, 자신을 제외한 3의 배수를 모두 지웁니다.
4. 남아있는 수 가운데 5는 소수이므로 자기 자신을 제외한 5의 배수를 모두 지웁니다.
5. 남아있는 수 가운데 7은 소수이므로 자신을 제외한 7의 배수를 모두 지운다.
6. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남게됩니다.

---

파이썬 코드

• 1 ≤ min ≤ 1,000,000,000,000
• min ≤ max ≤ min + 1,000,000

min의 범위를 보면 수가 굉장히 큽니다. 만약에 min에서 1,000,000,000,000 입력을 받고 , max의 최대값인 1,000,001,000,000를 입력받으면 1부터 1,000,001,000,000까지의 리스트를 만들어서 해야되는데, 공간도 너무 크고 시간도 너무 오래걸릴것입니다.

 

그러나 min과 max의 사이 거리는 1,000,000로 그다지 크지 않습니다. 그러므로 이 구간을 리스트로 만들어서 소수 구하는것과 비슷한 알고리즘을 적용시키면 됩니다.

기존 알고리즘은 소수하나의 배수들을 전부 없앴다면, 이번에는 수하나를 제곱해서 배수들을 전부 없앱니다.

그리고 그 수를 또 제곱해서 세제곱,네제곱 등을 만들고 역시 배수들을 전부 없앱니다.

당연히 리스트는 0부터가 아닌, min부터 입니다. 그래서 만약에 x의 수를 제거 할땐, x-min 인덱스로 접근해서 없애줍니다.

 

제곱수의 배수들을 없앨때, min max범위에 벗어난건 없앨필요 없고, 만약에 없애면 시간초과가 뜰 것입니다.

그러므로 그 제곱수의 상수(min / 제곱수)배를 우선 해주고 탐색을 시작합니다. -> min가 가까운 위치에서 시작해서 배수들을 제거할수 있습니다.

mn , mx = map(int, input().split())
num = [True] * (mx-mn+1)

for i in range(2,int(mx**0.5)+1):
    temp = i*i
    while temp <= mx:
        start_index = int(mn/temp) * temp
        for j in range(start_index , mx+1 , temp):
            if j < mn:
                continue
            if num[j-mn]:
                num[j-mn] = False
        temp*=i
result =0
for i in num:
    if i:
        result+=1
print(result)