[edu] 소수찾기 에라토스(프로그래머스 lv1)

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한 조건

• n은 2이상 1000000이하의 자연수입니다.

입출력 예

n	result
10	4
5	3

입출력 예 설명

입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

https://programmers.co.kr/learn/courses/30/lessons/12921

정답 1 (에라토스테네스의 체 이용, set 을 이용)

def solution(n):
    num = set(range(2, n+1))
    for i in range(2, n+1):
        if i in num:
            num -= set(range(i*i, n+1, i))
    return len(num)

정답 2 (에라토스테네스의 체 이용)

def solution(n):
    nums = [i for i in range(n+1)]
    for i in range(2, n+1):
        if not nums[i]:
            continue
        for j in range(i*i, n+1, i):
            nums[j] = 0
    return len([nums[i] for i in range(2, n + 1) if nums[i]])

짝수를 건너뛰기

def solution(n):
    nums = [i for i in range(n+1)]
    for i in range(3, n+1, 2):
        if not nums[i]:
            continue
        for j in range(i*i, n+1, i):
            nums[j] = 0
    return len([nums[i] for i in range(3, n + 1, 2) if nums[i]]) + 1

제곱근까지만 배수를 지우기(가장빠름)

def era(n):
    import math
    sq = int(math.sqrt(n))
    ns = [i for i in range(n+1)]
    for i in range(3, sq+1, 2):
        if ns[i] == 0:
            continue
        for j in range(i*i, n+1, i):
            ns[j] = 0
    return len([ns[i] for i in range(3, sq+1, 2) if ns[i]]) + 1

다른 알고리즘 과 비교

def is_prime(n):
    i = 2
    while i*i <= n:
        if not n % i:
            return False
        i += 1
    return True


def count_prime(n):
    cnt = 0
    for i in range(2, n+1):
        if is_prime(i):
            cnt += 1
    return cnt


def solution(n):
    nums = [i for i in range(n+1)]
    for i in range(2, n+1):
        if not nums[i]:
            continue
        for j in range(i+i, n+1, i):
            nums[j] = 0
    return len([nums[i] for i in range(2, n + 1) if nums[i]])


import time
n = 10000
start = time.time()
print("{} delay={}".format(solution(n), time.time()-start))
start = time.time()
print("{} delay={}".format(count_prime(n), time.time()-start))