[DAY-40] 백준 1929번 소수 구하기

1. 문제 

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

 

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

 

---

2. 문제 풀이 

import sys

N, M = map(int, sys.stdin.readline().split())

for i in range(N, M+1):
    if i == 1:
        continue
    for j in range(2, int(i**0.5)+1):
        if i % j == 0:
            break
    else:
        print(i)

 

깔깔 포인트...

M도 소수인지 확인 안해서 계속 틀림 ^_^; 

 

에라토스테네스의 체로도

문제 풀어보았어요

 

import sys
import math

N, M = map(int, sys.stdin.readline().split())

prime = [True for i in range(M+1)]
prime[0] = prime[1] = False

for i in range(2, int(math.sqrt(M))+1):
    if prime[i] == True:
        j = 2
        while i*j <= M:
            prime[i*j] = False
            j += 1

for i in range(N, M+1):
    if prime[i]:
        print(i)