백준 1929: 소수 구하기 (Python)

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

 

처음 코드 - 시간 초과

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

for i in range(m,n+1):
    k = 2
    cnt = 0

    if i == 1:
        cnt += 1

    while i > k:
        if i % k == 0:
            cnt += 1
            break

        k += 1

    if cnt == 0:
        print(i)

 

문제 설명에 에라토스테네스의 체라고 적혀있는걸 발견...!

그래서 바로 검색해보고 다시 알고리즘을 생각했다

 

m, n = map(int, input().split())
num = [i for i in range(m,n+1)]

for i in num:
    cnt = 0

    if i == 1:
        cnt += 1

    for p in range(2, int(i**0.5)+1):
        if i % p == 0:
            cnt += 1
            break

    if cnt == 0:
        print(i)

성공!

엇 근데 다시 보니까 리스트 왜 했지......ㅎ