소수 판별

def isPrime(num):
	for i in range(2, int(sqrt(num)) + 1):
		if num % i == 0:
			return False
	return True

출력값이 False이면 소수가 아닌 수.

시간복잡도는 O(루트N).

원리는 링크 참조

 

def sieve_of_eratosthenes(num):
    nums = [i for i in range(0, num + 1)]

    for i in range(2, num + 1):
        if nums[i] == 0:
            continue
        for j in range(2 * i, num + 1, i):
            nums[j] = 0
    
    return [x for x in nums if x != 0 if x != 1]

1부터 num까지의 소수를 알아내는 함수

에라스토테라스의 체 알고리즘