소수찾기 알고리즘 C++, 에라토스테네스의 체

 

소수란? 1보다 크고, 1과 자기 자신 외에는 나누어지지 않는 수를 말한다. 

(예 : 2, 3, 5, 7, 11, 13 ....)

🧩 기본 소수 판별 (Brute Force)

• 하나의 수n에 대해 2부터 √N까지 나눠보며 소수인지 판단. 
• 시간복잡도 : O(√N)

✅ 작거나 단일 수 하나만 판단할 때 적합. 

bool is_prime(int n){
	if(n<2) return false;
	for(int i = 2; i*i<=n; i++){
    	if(n%i == 0) return false;
    }
    return true;
}

 

 

 

💡 에라토스 테네스의 체란? 

 

에라토스테네스의 체는 소수를 빠르게 구하는 고전적인 알고리즘이다. 

특히 1부터 N까지의 소수를 구할 때 매우 효율적이다. 

 

에라토스테네스의 체 알고리즘은 다음과 같다. 

1. 2부터 N까지의 모든 자연수를 나열한다. 
2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다. 
3. 남은 수 중에서 i의 배수를 모두 제거한다.(i는 제거하지 않는다.)
4. 더 이상 반복할 수 없을 때까지 2번과 3번 과정을 반복한다. 

예를 들어, 

1~30까지의 수가 있다고 가정할 때의 알고리즘은 다음과 같이 진행된다. 

1. 처음엔 2부터 시작  ⋙ 2의 배수 제거 

2. 다음 수 3  ⋙ 3의 배수 제거 

3. 다음 수 4의 배수 제거 

 

이 과정을 √N까지 반복하면, 남아있는 수는 모두 소수다. 

 

에라토스테네스의 체 알고리즘의 시간 복잡도는 O(N log log N)으로 사실상 선형 시간에 동작할 만큼 매우 빠르기 때문에 1,000,000이하 소수를 구할 떄도 실전에서 자주 사용한다. 

vector<int> is_prime(N+1,1), primes;
is_prime[0] = is_prime[1] = 0;

for(int i = 2; i<= N ; ++1){
	if(is-prime[i]) primes.push_back(i);
    for(int p:primes){
    	if(i * p > N) break;
        is_prime[i*p] = 0;
        if(i%p == 0)break;
    }
}