에라토스테네스의 체 #소수

0~size-1까지의 모든 숫자들에 대해서 소수인지를 판별

 

1. isNotPrime는 소수인것이 0

int isNotPrime[size];

void eratosthenes(size) {
    isNotPrime[1] = 0;
	isNotPrime[1] = 1; // 0과 1은 소수가 아니다.
	for (int i = 2; i*i < size; i++) { 
		if (!isNotPrime[i]) { //소수이거나, 아직 탐색을 안했다면 (isNotprime은) 0
			for (int j = i * i; j < size; j += i) { 
				isNotPrime[j] = 1;
			}
		}
	}
}

 

2. isPrime는 소수인것이 1

#에라토스테네스

isPrime=[1 for i in range(size)]
def prime():
    isPrime[0]=isPrime[1]=0
    for i in range(2,size):
        if isPrime[i]:
            for j in range(i*i,maxNum+1,i):
                isPrime[j]=0

 

* 에라토스테네스체의 시간복잡도는 O(N*log(log(N)))