[코테 알고리즘] 소수 판별&투 포인터 / 관련 문제

소수 판별

에라토스테네스의 체

import math

# 2부터 1000까지의 모든 수에 대하여 소수 판별
n = 1000
array = [True for i in range(n+1)]

# 에라토스테네스의 체 알고리즘 수행
# 2부터 n 제곱근까지의 모든 수 확인
for i in range(2, int(math.sqrt(n)) + 1):
    if array[i] == True: # i가 소수인 경우
        # i를 제외한 i의 모든 배수 지우기
        j = 2
        while i * j <= n:
            array[i * j] = False
            j += 1

# 모든 소수를 출력
for i in range(2, n+1):
    if array[i]:
        print(i, end=" ")

• 시간 복잡도
  • O(NloglgoN)
• 공간복잡도
  • 각 자연수에 대한 소수 여부를 찾아야하므로 비 효율적

 

문제

소수구하기

[백준] 1929번 파이썬 - 에라토스테네스의 체

import sys
input = sys.stdin.readline

from math import sqrt

start, end = map(int, input().split())

num = [i for i in range(end + 1)]

num[0] = 0
num[1] = 0

for i in range(2, int(sqrt(end)) + 1):
    if num[i] == 0:
        continue
    for j in range(i + i, end + 1, i):
        num[j] = 0

for i in range(start, end + 1):
    if num[i] != 0:
        print(num[i])

• 에라토스테네스의 체의 원리
  1. 구하고자 하는 소수의 범위만큼 1차원 리스트를 생성
  2. 2부터 숫자를 시작해 숫자가 지워지지 않은 경우 현재 선택된 숫자의 배수에 해당하는 수를 탐색하며 지운다.단, 처음 선택된 수는 지우지 않는다.
  3. 리스트를 반복한다.

 

투 포인터

• 리스트에 순차적으로 접근해야할 때 두 개의 점 위치를 기록하면서 처리하는 알고리즘
  • 리스트에 담긴 데이터에 순차적으로 접근해야할 때
  • 시작점과 끝점 2개의 점으로 접근할 데이터의 범위 표현