에라토스테네스의 체 (소수 구하기)

Dong-Hyeon Park·2022년 3월 29일
0

Python Skills

목록 보기
3/7

O(N^1/2)의 시간 복잡도로 소수를 구할 수 있다.

수의 범위를 정하고, 2부터 최대 수까지의 배수를 배열에서 제거함 (자기 자신은 제외)

prime_number = [i for i in range(1, N + 1)]
for i in range(2, N + 1):
	num = i
    for j in range(2, limit // num + 1):
        if num * j in prime_number:
        	prime_number.remove(num * j)        
profile
Android Engineer from KU CSE

0개의 댓글