백준 1929번

n=int(input())
m=int(input())

def is_prime_num(n):
    arr = [True] * (n + 1) # 특정 수가 지워졌는지 아닌지 확인하기 위한 배열
    arr[0] = False
    arr[1] = False

    for i in range(2, n + 1):
        if arr[i] == True: # 특정 수가 지워지지 않았다면 (소수여서)
            j = 2

            while (i * j) <= n:
                arr[i*j] = False # i의 배수의 값을 False로 지워준다.
                j += 1

    return arr

arr = is_prime_num(m) # 0 ~ 50중 소수를 구하기 위한 함수

for i in range(len(arr)):
    if n<3:
        continue
    if arr[i] == True:
        print(i, end=' ')

 

인터넷에 비슷한 알고리즘을 검색해서 제출하였다.

문제는 런타임에러

이유는 소수를 구할때 제곱근까지만 구해도 되기때문이다.

그래서 수정된 코드를 보았다.

 

출처:https://velog.io/@yj_lee/%EB%B0%B1%EC%A4%80-1929%EB%B2%88-%EC%86%8C%EC%88%98-%EA%B5%AC%ED%95%98%EA%B8%B0-%ED%8C%8C%EC%9D%B4%EC%8D%AC

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

for i in range(m,n+1):
    if i==1:#1은 소수가 아니므로 제외
        continue
    for j in range(2,int(i**0.5)+1):
        if i%j==0: #약수가 존재하므로 소수가 아님
            break   #더이상 검사할 필요가 없으므로 멈춤
    else:
        print(i)

int(i**0.5)라는 부분이 보일 것이다.

이것으로 제곱근을 구한뒤 제곱긑까지만 계산을 시킨것이다.