[edu] 소수 구하기

[소수구하기]

약수가 1, 자기자신 밖에 없는 정수 (1은 소수아님)

def prime_b(num):
    for i in range(2, num):
        if num % i == 0:
            return False
    return True

prime_b 는 3만개가 넘어가면 많이 느려진다.

def prime_a(num):
    i = 2
    while i*i <= num:
        if num % i == 0 :
            return False
        i+=1
    return True

prime_a 는 수십배 빨라진 성능을 보여준다.

def is_prime(num):
    i = 2
    while i*i <= num:
        if not num % 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


import time
start = time.time()
print(count_prime(50000))
print("delay={}".format(time.time()-start))