[백준 1978] 소수찾기 C++

https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

백준 1978 소수찾기 문제

#include <iostream>
#include <cmath>

using namespace std;

#define MAX 1001 // 문제에서 1000이하의 자연수
int N;

int input_arr[MAX]; // 입력 받을 자연수의 배열

bool Notsosu[MAX];  //소수가 아니라면 true, 소수가 맞다면 false

int result; // 총 개수

void calculate_sosu() {

	Notsosu[0] = true; // 0과 1은 소수가 아님으로 초기값 셋팅
	Notsosu[1] = true;

	int square_root = (int) sqrt(MAX - 1); // sqrt(N)까지만 계산
	for (int i = 2; i <= square_root; i++) {
		int num = i;
		
		if (Notsosu[i] == true) continue; // 이미 계산한 연산이라면 패스

		while (num < MAX - 1) { // 계산하는 최대 범위가 넘어갔을 때 break
			
			num += i;			//배수 구하기

			Notsosu[num] = true; // 배수들은 전부 true표시
		}
		
	}

}
void input() {

	cin >> N;
		
	for (int i = 0; i < N; i++) {
		cin >> input_arr[i];
	}
	
	calculate_sosu();


}
void solution() {

	for (int i = 0; i < N; i++) {

		if (!Notsosu[input_arr[i]]) result++;


	}

}
void solve() {


	input();
	solution();

	cout << result << '\n';


}


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

	solve();


	return 0;
}

백준사이트에서 소수 찾기에 대한 풀이입니다.

[풀이]

소수란, 자기 자신보다 작은 두 자연수를 곱하여 만들 수 없는 1보다 큰 자연수 입니다. 

이 말은 즉, 어떤 수의 약수가 1과 자기 자신밖에 없다는 거죠. 

그렇다면 1과 자기 자신밖에 없으면 작은 수부터 시작했을 때 배수가 되는 수들은 다 지워주면 소수만 남게되는 특징을 이용했습니다.

 

이 이론은 에라토스테네스의 체를 이용하여 쉽게 풀 수 있습니다.

 

	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

 

위의 표는 에라토스테네스의 체를 이용해서 100까지 소수를 구하여 2, 3 4, ....작은 수부터 배수를 전부 다 지워서 나온 결과 입니다.

 

이 때 100까지의 소수를 알고 싶을 때 수를 어디까지만 계산해야되는 문제가 있습니다. 

 

11은 소수이고 11 x 11 은 121이기 때문에, 즉 2부터 11까지 공배수를 구했을 때 각각의 배수별로 배수를 다 지웠기 때문에 N * N < 최대 크기가 되는 N만큼만 배수를 구하시면 됩니다.

따라서, 위의 그림은 100까지 소수를 찾는 그림이기 때문에 11 * 11 = 121 즉, 10까지만 배수를 찾으면 100의 모든 소수를 찾을 수 있습니다. 

 

저는 1000까지의 소수를 미리 다 찾은다음에 소수가 몇개 있는지 계산했습니다.

 

 최대 1000이라고 했을 때 1000개의 값을 다 구한 뒤 계산하기 때문에 시간 복잡도는 O(루트(N))이 나오게 됩니다.

 

sqrt(N)만큼만 계산하고 입력 배열에서 소수인지만 보기만 하면 되니까요^^