[알고리즘] 소수 판별

에라토스테네스의 체

---

• 특정 수 미만인 소수를 구하는 알고리즘
• 알고리즘
  • 크기가 n+1인 배열을 생성한다.
  • 특정 인덱스의 배수에 해당하는 수를 지운다.(자기자신 제외)
    • ex) idx : 2 -> 2,4,8,...을 삭제
  • 인덱스를 1씩 증가시키며 2번 과정을 반복한다.(2~n)
  • 남은 수를 출력한다.

예제

---

1. 백준 1929

• 소수 구하기
• [M,N] 범위의 소수를 모두 출력하는 프로그램을 작성하시오

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

# 인덱스가 [min, max]인 부분만 사용
prime_numbers = [0]*(max+1)

prime_numbers[1]=1
# 해당 인덱스의 값이 0 : 소수 / 1 : 소수x
for i in range(2,max+1) :
  if prime_numbers[i] == 1 :
    continue
  for j in range(i+i, max+1, i) :
    prime_numbers[j] = 1
    

for i in range(min,max+1):
  if prime_numbers[i] == 0 :
    print(i)

2. 백준 4948

• 베르트랑 공준
• 임의의 자연수 n에 대하여 (n,2n] 범위의 소수의 개수를 출력하시오

min = 1
while True :
  min = int (input())
  if min == 0 : break
  max = min * 2
  
  # 인덱스가 [min, max]인 부분만 사용
  prime_numbers = [0]*(max+1)

  # 0과 1은 소수가 아님
  prime_numbers[0]=1
  prime_numbers[1]=1
  
  # 해당 인덱스의 값이 0 (소수) / 1 (소수x)
  for i in range(2,max+1) :
    if prime_numbers[i] == 1 :
      continue
    for j in range(i+i, max+1, i) :
      prime_numbers[j] = 1

  count = 0
  for i in range(min+1, max+1) :
    if prime_numbers[i] == 0 :
      count += 1
  """
  sum으로 개수를 구할 수도 있음
  
  count = sum(prime_numbers[min+1 : max+1])
  
  """
  print(count)