⏰ 시간 초과

import math
min, max = map(int,input().split())

# 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때
# X는 제곱 ㄴㄴ수

# 제곱수 예시) 4, 9, 16, 25 ....
# 제곱 ㄴㄴ 수) 2, 3, 5, 6, 7, 8, 10

sqrt_arr = []

# 제곱수를 찾고 배열에 넣어두자
for i in range(2, int(math.sqrt(max)) + 1):
    sqrt_arr.append(i * i)

cnt = 0
for i in range(min, max+1):
  is_not_square = True
  for n in sqrt_arr:
    if(i%n ==0):
      is_not_square = False
      break
  if is_not_square:
    cnt += 1

print(cnt)

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

🏁 에라토스테네스체

 특정 범위 내의 모든 소수(Prime Number)를 빠르고 효율적으로 찾아내는 알고리즘

해당 수보다 작은 모든 수로 나누어 보아서 소수인지 판단하는 방법

에라토스테네스의 체 : 범위에서 합성수를 지우는 방식으로 소수를 찾는 방법.

1. 1은 제거
2. 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다.
3. 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다.
4. 지워지지 않은 수 중 제일 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 지운다.
5. (반복)

💡 아이디어

1. 체의 범위 min부터 max까지의 수를 배열의 크기로 잡는다
2. 제곱수의 범위
   ****어떤 수 X가 제곱수로 나누어떨어지려면, X를 나누는 가장 작은 제곱수는 $2^2 = 4$부터 시작합니다.
   - 나누는 수인 $i^2$이 max보다 커지면 더 이상 검사할 필요가 없음
   - 따라서 i는 2부터 $\sqrt{max}$까지만 확인하면 됩니다. $\sqrt{10^{12}}$는 1,000,000이므로, 이 정도는 충분히 반복문으로 돌릴 수 있는 수치

→ 여기까지는 아이디어 똑같음. 어디서부터 문제였냐면?

시간초과가 나는 이중반복문 구조

for i in range(min, max+1):
  is_not_square = True
  for n in sqrt_arr:
    if(i%n ==0):
      is_not_square = False
      break
  if is_not_square:
    cnt += 1

1. 시작점 찾기

   에라토스테네스의 체에서 2의 배수를 지울 때 2, 4, 6...순으로 가듯이, 여기서도 $i^2$의 배수들을 지워나가야 합니다. 그런데 우리는 min부터 시작하므로, min보다 크거나 같은 $i^2$의 배수 중 가장 작은 값을 찾아야 합니다.

   • 수식 힌트: min을 $i^2$으로 나눈 몫을 이용해 보세요.
   • 만약 min이 $i^2$으로 나누어떨어지지 않는다면, (min / i^2 + 1) * i^2이 첫 번째 시작점이 됩니다.
   • 이 시작점부터 $i^2$씩 더해가며 max까지 체크(True/False)를 표시하면 됩니다.

하나씩 지워나가는 것이 아니라 배수 통째로 지우기

⏰ 시간초과2

import math
min, max = map(int,input().split())

sqrt_arr = []

for i in range(2, int(math.sqrt(max)) + 1):
    sqrt_arr.append(i * i)

num_list = []
for i in range(min, max+1):
    num_list.append(i)

for s in sqrt_arr:
  for x in num_list:
    if(x%s == 0):
      num_list.remove(x)

print(len(num_list))

시간 복잡도 측면에서 max값이 커질 때(최대 1조) 버티지 못하는 구조예요. 특히 num_list.remove(x)는 리스트를 처음부터 끝까지 훑어야 해서 아주 느리고, num_list 자체를 1:1로 만드는 방식은 메모리 부족(Memory Error)을 일으키기 쉽다.

리스트 remove

이미 제곱ㄴㄴ수가 아닌 수에 대해서 검사를 하지 않도록 remove를 사용하였으나,

list.remove() 의 경우 호출하려면 리스트를 처음부터 끝까지 훑어야하며, 리스트 재배치 문제로 인해 모든 데이터를 한 칸씩 앞으로 당겨오는 작업을 한다.

리스트 직접 접근

is_sq_free[j - min] = False

이 코드의 경우 리스트가 아무리 길어도 list[index]는 직접접근이므로 O(1)이고 데이터 이동이 없다.

🥹정답코드

import math
min, max = map(int,input().split())

is_sq_free = [True] * (max - min + 1)

for i in range(2, int(math.sqrt(max)) + 1):
    square = i * i
    
    # square의 배수 중 min보다 크거나 같은 첫 번째 배수 찾기
    # 예: min이 10이고 square가 4라면, 10//4 = 2, start = 4 * 3 = 12
    start = math.ceil(min / square) * square

    for j in range(start, max + 1, square):
        if is_sq_free[j - min]:
            is_sq_free[j - min] = False
            
print(sum(is_sq_free))