소수 구하는 함수 (파이썬)

 

 

백준 풀면서 짜본 소수 구하는 함수.

나중에 더 효율적인 코드를 짜게 되면 업데이트할 예정.

 

 

(아래 코드는 2022.06.28일 기준.)

# n이하의 소수를 모두 포함한 리스트 출력.
def prime(n):
    ans = list(range(2,n+1))
    for i in list(range(2,n+1)):
        for z in range(2, int(i**(1/2))+1):
            if (i%z == 0):        
                ans.remove(i)
                break               
    return ans

 

 

 

+ 에라토스테네스의 체를 이용한 소수 구하는 함수 (위의 코드보다 효율적) (2022.06.29)

# n 이하가 아닌 n 미만의 소수 찾는 함수임을 주의!!
def prime_list(n):
    # 초기화: n개 요소에 True 설정(소수로 간주)
    ans = [True] * n

    
    for i in range(2, int(n ** 0.5) + 1):
        if ans[i] == True:              # i가 소수인 경우
            for j in range(2*i, n, i):  # i이후 i의 배수들을 False 판정
                ans[j] = False

                
    # 소수 목록 추출.
    return [i for i in range(2, n) if ans[i] == True]