[백준] 1929번 소수구하기

⛏ 문제 파악

• M 이상 N 이하의 소수를 모두 출력하는 프로그램
• 일렬로 출력되어야한다.

👉🏻  답안

 

• 에라토스테네스의 체 그 자체인 코드

 

M , N = map(int, input().split())

sieve = [True] * (N + 1)
sieve[0] = False
sieve[1] = False

for i in range(2, N + 1):
    if sieve[i]:
        for j in range(i + i, N + 1, i):
            sieve[j] = False
for i in range(M, N + 1):
    if sieve[i]:
        print(i)

• 소수인지 판별하는 함수 만들어 바로 출력

M , N = map(int, input().split())

def isPrime(num):
    if num==1:
        return False
    else:
        for i in range(2, int(num**0.5)+1):
            if num%i == 0:
                return False
        return True

for i in range(M, N+1):
    if isPrime(i):
        print(i)

📑  간단한 설명

• 에라토스테네스의 체를 이용하여 소수를 구하면 되는 문제였다.
• 어줍잖게 체를 따라하는 것보다, 그냥 기존에 있는 에라토스테네스의 체를 사용하는게 효율이 더 좋다...!

 

• 번외 (다른 사람 답안인데 동일한 맥락인데 다른 방식임)

x, y = map(int, input().split())

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