bitmask 를 이용한 에라토스테네스의 체

만약 k라는 숫자를 8로나눈 나머지를 구하고 싶다.

k%8 --> k&(8-1) 

 

boolean 배열을 비트로 이용해 풀고 싶다.

unsigned char v[(MAX_N+7) / 8] ; 

 

 

에라토스테네스의 체

제곱근 까지 돌리고 -> 만약 i가 소수라면 -> i*i미만의 배수는 이미지졌으므로 i*i 부터 N까지 배수들을 지워준다.

 

#include <iostream>
#include <vector>

using namespace std;

int MAX_N,n;
unsigned char *sieve;

//k가 소수인지 확인한다.
inline bool isPrime(int k) {
	return sieve[k >> 3] & (1 << (k & 7)); // 0 이면 false 0이 아니면 true이다.
}
//k가 소수가 아니라고 표시한다. -> 즉 0으로 바꿔주는 것임
inline void setComposite(int k) {
	sieve[k >> 3] &= ~(1 << (k & 7));
}
int main() {
	cin >> MAX_N >> n;
	sieve = new unsigned char[(MAX_N + 7) / 8];
	memset(sieve, 255, sizeof(sieve)); // 8비트를 모두 1로 바꿔줌
	setComposite(0);
	setComposite(1);
	int sqrtn = int(sqrt(n));
	for (int i = 2; i <= sqrtn; ++i) {
		//이 수가 아직 지원지지 않았다면
		if (isPrime(i)) {
			//i의 배수 j들에 대해 isPrime[j] = false 로 둔다.
			//i*i 미만의 배수는 이미 지워졌으므로 신경 쓰지 않는다.
			for (int j = i * i; j <= n; j += i) {
				setComposite(j);
			}
		}
	}
	(sieve[n > 3] & (1 << (n & 7))) ? cout<<"true" : cout<<"false";
}