[Algorithm] 소수 구하기

소수란 1과 자기 자신만으로 나눠 떨어지는 수를 말합니다.

그리고 그 소수를 구하는 가장 간단한 방식은 에라토스테네스의 체라는 알고리즘을 이용하는 것입니다. 

알고리즘은 다음과 같습니다.

1. 0,1은 소수가 아님

2. 2는 소수임, 그리고 2의 배수가 되는 수들 (2,4,6,8,10,12 ...) 목록에서 제외

3. 3은 소수임, 그리고 3의 배수가 되는 수들 (9,15,21....) 목록에서 제외 *(6, 12, 18 ... 등은 이미 제외)

4. 4는 이미 제외됨

    ... 

다음은 이 알고리즘을 구현한 코드입니다. 각 숫자를 표현하는 데 있어서 비트마스크를 이용한 것과 2가지 최적화 방법이 적용되 있는 걸 눈여겨 보세요. 

첫 번째 최적화는 어떤 N이 소수인지 판별하는 데 있어서 N까지의 모든 수를 따지는 게 아니라 N의 제곱근까지만을 확인하는 것입니다. 

두 번째 최적화는 어떤 소수 i의 배수에 해당하는 수를 제외할 때 i*i부터 시작한다는 겁니다. 왜냐하면 i*i' (i' < i) 꼴의 수들은 이미 알고리즘에 의해서 제외되었기 때문이죠.

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

#define MAX_N 500
unsigned char sieve[(MAX_N + 1)/8];

void set_composite(int n){
	sieve[n >> 3] |= (1 << (n % 8));
}

bool is_prime(int n){
	return !(sieve[ n >> 3] & (1 << (n % 8)));
}

void prime() {
	memset(sieve, 0, sizeof(sieve));
	set_composite(0);
	set_composite(1);

	int sqrtn = sqrt(MAX_N);
	for(int i=2; i<=sqrtn; ++i){
		if(is_prime(i)){
			for(int j = i*i; j <= MAX_N; j += i){
				set_composite(j);
			}
		}
	}
}

void print_prime(){
	for(int i=0; i<MAX_N; ++i){
		if(is_prime(i))
			cout << i << " ";
	}
	cout << endl;
}

int main(void)
{
	prime();
	print_prime();
}

결과

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499

출처 : 알고리즘 문제해결 전략 2권