[백준_python] 소수 구하기 || 1929

www.acmicpc.net/problem/1929

1929번: 소수 구하기

2부터 쭉 나눠보기

# 소수 구하기
# ? 시간 초과
m, n = map(int, input().split(' '))

arr = [i for i in range(m, n+1)]

for i in arr:
   if i == 1:
       continue
    if i == 2:
        print(i)
        continue
    cnt = 0
    for j in range(2, i):
        if i % j == 0:
            cnt += 1
    if cnt == 0:
        print(i)

시간 초과 발생!!

---

에라토스테네스의 체

해당하는 숫자의 약수 중간값까지 약수의 배수들을 모두 지워나가는 방식.
해당하는 숫자의 약수들은 각각 서로 쌍을 이룰 수 있다. 예를 들어, 6이라고 한다면,
1, 2, 3, 6 이므로, 16과 23처럼 쌍을 이룰 수 있다.
따라서 2부터 루트 6까지 검색하며, 배수들을 모두 지워나간다.
 

def isprime(num):
    if num == 1:
        return False
    else: #else안에 안넣어줘도 됨
        for i in range(2, int(num**0.5)+1):
            if num % i == 0:
                return False
        return True


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

for i in range(m, n+1):
    if isprime(i):
        print(i)

num을 제곱근으로 바꿔주어 그 값까지 나눠떨어지는 지 검사하거나,
반대로 검사해주는 값을 제곱해준다.

# 소수 구하기_3

def isprime(num):
    if num == 1:
        return False
    i = 2
    while i*i <= num:
        if num % i == 0:
            return False
        i += 1
    return True

m, n = map(int, input().split(' '))
for i in range(m, n+1):
    if isprime(i):
        print(i)