39. 소수 찾기 ★ (소수 판별 알고리즘)

유형 : 구현 (소수 판별)

풀이 시간 : 15분 -> 인터넷 서치

 

 

소수 판별을 효율적으로 하려면, 에라스토테네스의 체 원리를 이용해야 한다. 

 

1. 기본 : set, 에라스토테네스의 체 이용하기 

def solution(n):
    answer = set([i for i in range(2, n+1)])
    for i in range(2, int(n ** 0.5) + 1):
        if i in answer:
            mul = set([x for x in range(i*2, n+1, i)])
            answer -= mul
    return len(list(answer))

 

- 체크 (순회) : n ** 0.5 + 1 / math.sqrt(n) +1 까지만 하면됨,

- answer에 있다면 체크

  => i의 배수 set 만들기

  => answer에서 빼 주기

 

2. 더 효율적인 알고리즘 : list 사용 

 초기값 = True

 소수가 아님이 확인되면 = False

def solution(n):
    answer = [True for i in range(0, n+1)]
    answer[0], answer[1] = False, False 
    for i in range(2, int(n ** 0.5) + 1):
        if answer[i] == True:
            for x in range(i*2, n+1, i):
                answer[x] = False    
    return list(answer).count(True)