C++을 사용한 소수찾기 (에라토스테네스의 체) / Wanna Be 컴잘알

소수 찾기는 알고리즘 문제에서도 자주 출제되는데, 소수 찾는 방법에 대해서 정리해 보고자 한다.

아마 두가지 부류의 소수 찾는 경우가 있을 것이다.

 

첫번째는 N은 소수인가 아닌가? 판별하는 경우이고 두번째는 1~N까지의 양의 정수 중에 소수를 출력하는 경우

 

Q. 첫번째 : 특정 N은 소수인가? 

이 경우에는 2부터 N의 제곱근 까지 탐색을 하면된다. 

 

-코드-

#include "pch.h"
#include <iostream>
#include <math.h>

using namespace std;

int main() {

	int N;
	cin >> N;
	bool sosu_flag = false;

	for (int i = 2; i <= sqrt(N); i++) {
		if (N%i == 0) {
			sosu_flag = true;
			break;
		}
	}
	
	if (sosu_flag) {
		cout << "소수가 아닙니다.";
	}
	else {
		cout << "소수입니다.";
	}

	return 0;
}

 

-실행 결과-

 

Q. 두번째: 1~N까지의 양의 정수 중에서 소수를 출력해보아라.

 

이 경우에 에라토스테네스의 체라는 알고리즘을 사용하게 된다. 해당 알고리즘은 N까지 소수를 출력해보라는 경우에  다음과 같은 컨셉을 가지고 한다.

 

1. 2~N의 제곱근의 반복 범위를 가지고 있다.

2. 현재 예를 들어 3일 경우 자신을 제외한 3의 배수들을 모두 소수가 아니라고 판별한다.

3. 그래서 2의 체로 거르고 3의 체로 거르고 ..... N의 제곱근의 체로 까지 거르고 남은 수들이 소수인 것이다.

 

-코드-

#include  "pch.h"
#include <iostream>
#include <math.h>
#include <string.h>

using namespace std;

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

	int n;
	cin >> n;

	bool *sosu = new bool[n + 1];
	memset(sosu, false, sizeof(bool)*(n + 1));

	for (int i = 2; i <= int(sqrt(n)); i++) {
		if (sosu[i] == false) {
			for (int k = i * 2; k <= n; k += i) {
				sosu[k] = true;
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		if (sosu[i] == false) {
			cout << i << " ";
		}
	}

	return 0;
}

-실행 결과-