백준 1978번 - 소수 찾기

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

1978번: 소수 찾기

사고과정)

우선 소수라는 개념 자체가 '1과 자기 자신만으로 나뉘어지는 수' 라고 학교 다닐 때 배웠다.

그렇다면 그 이외의 숫자들로 나뉘어지면, 그건 소수가 아닐 것이다. 를 활용했다.

예외사항으로 1은 소수가 아니고.

#include <iostream>

using namespace std;

int main()
{
	int N;
	cin >> N;

	int wrong = 0;
	for (int i = 0; i < N; i++)
	{
		int num;
		cin >> num;
		if (num == 1)
		{
			wrong++;
			continue;
		}
		for (int j = num - 1; j > 1; j--)
		{
			if (num % j == 0)
			{
				wrong++;
				break;
			}
		}
	}
	cout << N - wrong;
	return 0;
}

소수가 아닌 경우를 count 한 다음에, (전체 입력받은 숫자 갯수 - 소수가 아닌경우)를 출력하는 걸로 했다.

추가) 문제 알고리즘 분류에 보면 '에라토스테네스의 체'라는 알고리즘이 있다.

소수를 조금 더 효율적으로 찾는 알고리즘인데, 이는 내가 바로 다음 포스트에 공부해서 올리겠다!