[python] 1929_소수 구하기

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

해결 방법

소수를 판별하는 방법은 크게 아래 3가지가 있다.

1. 간단한 방법
2. 제곱근
3. 에라토스테네스의 체

간단한 방법
👉2~n-1까지 전부 나눠보기

def prime(n):
    for i in range(2,n):
        if n % i == 0:
            return False
        return True

2부터 n-1까지 전부 나눠보며 나머지가 0이라면 즉, 나누어 떨어진다면 약수가 있다는 뜻이므로 해당 수는 소수가 아니게 된다.

제곱근
👉n의 약수 계산 범위를 줄이는 방법
👉몫과 나누는 값의 대칭을 이용해 제곱근 까지만 약수 검사를 한다.

import math
def prime(n):
    for i in range(2,int(math.sqrt(n))+1):
        if n % 1 == 0:
            return False
    return True

에라토스테네스의 체
👉여러 수에 대해 소수 판별의 해야 하는 상황에 사용 가능
👉에라토스테네스의 체에 대해

아래 제출 코드 참고

제출

💡제곱근 이용 코드

시간: 5324ms

import math
m,n=map(int,input().split())

for i in range(m,n+1): #n부터 m까지 반복
    if i==1: #1은 소수가 아니므로
        continue #제외
    for j in range(2,int(math.sqrt(i))+1): #제곱근까지
        if i%j==0: #나누어 떨어지면 약수가 존재하므로
            break #다음 i로
    else:
        print(i) #약수가 없다면 출력

💡에라토스테네스의 체 이용 코드

시간: 284ms

m,n=map(int,input().split())

arr = [True]*(n+1) #리스트 생성
arr[0] = False
arr[1] = False

for i in range(2,int(n**0.5)+1): #2부터 n의 제곱근까지
    if arr[i]: #i가 남은 수인 경우
        for j in range(i*2,n+1,i): #range(start, stop, step)
            arr[j] = False
            
#소수 출력            
for i in range(m,n+1):
    if arr[i]:
        print(i)

👉range(i*2,n+1,i)
range에 step값까지 적는 코드는 처음 써봤다. i*2부터 n까지 i를 간격으로 전부 False처리하는 것으로 약수가 있는 수를 제거하는 것이다.

메모

어떤 알고리즘을 쓰냐에 따라 시간 차이가 이렇게 난다(o′┏▽┓｀o) 한 문제를 여러 방법으로 풀어보는 연습을 꾸준히 하자.