[구름 알고리즘 먼데이 챌린지] Week1 : 4. 소수 찾기

간단한 소수 판별 문제로 볼 수 있고 어렵지 않게 해결할 수 있었다.

 

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

int n, a, ans;

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

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a;
		if (is_prime(i)) ans += a;
	}

	cout << ans;
	return 0;
}

---

문제를 해결한 후 해설을 통해 에라스토테네스의 체 이론을 적용하여 더 효율적으로 해결할 수 있다는 것을 알게 되었다.

 

에라스토테네스의 체

에라스토테네스의 체를 간략하게 설명하자면 2부터 루트n까지 반복하여 해당 수a를 소수로 가정하고 범위 내 a의 모든 배수들을 소거하여 불필요한 소수 판별을 줄이는 알고리즘이다.

출처:https://donggoolosori.github.io/2020/10/16/eratos/

---

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

int n, a, prime[100001], ans;

void erato() {
	prime[0] = true, prime[1] = true;
	for (int i = 2; i < sqrt(n); i++) {
		if (prime[i] == false) {
			for (int j = i + i; j <= n; j += i) {
				prime[j] = true;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n;
	erato();
	for (int i = 1; i <= n; i++) {
		cin >> a;
		if (!prime[i]) ans += a;
	}

	cout << ans;
	return 0;
}

---

에라스토테네스의 체 비트마스킹 구현

//https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=occidere&logNo=220973318428
#include <iostream>
#include <math.h>
#include <cmath>
using namespace std;
#define MAX_N 100000000
int n, a, ans;
unsigned char sieve[(MAX_N + 7) / 8];

//k가 소수인지 확인
inline bool isPrime(int k) {
	//소수이면 1, 합성수면 0 리턴
	//sieve[k >> 3]은 sieve[k / 8]과 동일 -> bit 연산이 더 빠름.
	//(1 << (k & 7)) -> k & 7은 k % 8과 동일
	return sieve[k >> 3] & (1 << (k & 7));
}

//k가 소수가 아니라고 표시
inline void setNotPrime(int k) {
	sieve[k >> 3] &= ~(1 << (k & 7));
}

void erato() {
	memset(sieve, 255, sizeof(sieve)); //모든 비트 1로 초기화
	setNotPrime(0); //0과 1은 소수가 아니므로 비트를 0으로 변경
	setNotPrime(1);

	int sqrtn = int(sqrt(MAX_N));
	for (int i = 2; i <= sqrtn; ++i)
		if (isPrime(i))
			for (int j = i * i; j <= MAX_N; j += i)
				setNotPrime(j);
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin >> n;
	erato();
	for (int i = 1; i <= n; i++) {
		cin >> a;
		//자릿수 i가 소수이면 해당 수 더하기
		if (isPrime(i)) ans += a;
	}

	cout << ans;
	return 0;
}