20210615 TIL

알고리즘 문제를 풀면 소수문제가 상당히 많이 나오는 것 같다.

그래서 기본적으로 소수 구하는 공식을 정리해 적어보려 한다.

기본 소수 구하는 알고리즘

def find_prime_list_under_number(number):
    prime_list = [] # 빈 리스트

    for n in range(2, number + 1): #소수는 2부터 
        for i in prime_list:
            if n % i == 0 and i * i <= n # prim_ist의 i의 제곱이 n보다 작을 때
                break
        else:
            prime_list.append(n)

    return prime_list

에라토스테네스의 체를 활용

def prime_list(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

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