백준 1978번 : 소수 찾기

dldzm·2021년 1월 28일
0

알고리즘 공부

목록 보기
18/42
post-thumbnail

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

소수 찾기.

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

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

int main() {
	int num, elem, total = 0;
	cin >> num;
	for (int i = 0; i < num; i++) {
		cin >> elem;
		if (prime(elem))
			total++;
	}
	cout << total << endl;
	
	return 0; 
}

소수 찾는 알고리즘을 살펴보자.

if (n <= 1)
	return false;
        

자연수 1보다 큰 수를 기준으로 소수를 판별하므로 1 이하인 수는 return false를 한다.

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

2부터 시작하여 sqrt(n)까지 진행한다. sqrt(n)까지 진행하는 이유는 다음과 같다. 예를 들어 15의 경우 (1x15), (3x5), (5x3), (15x1)과 같이 거울 상처럼 어느 순간부터 두 숫자의 위치가 바뀐 곳이 등장한다. 이 거울의 위치가 되는 곳이 sqrt(15) 이므로 이 이후를 넘어가면 중복 탐색이다.

나머지 부분은 나머지 연산자를 이용해 (n % i) == 0) == true 가 나오는 경우 소수가 아니므로 return false해준다. 나눠진다는 말은 자기 자신과 1 외에도 다른 수로 곱해질 수 있다는 뜻이기 때문이다.

길게 쓴 이유는 한번에 통과하지 못했기 때문..

profile
🛰️ 2021 fall ~

0개의 댓글