BackJoon 1978 소수 찾기

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

소스결과 1984 KB / 0 ms

출처 Baekjoon

언어 C++ 17

분류 수학, 에라토스테네스의 체

 

설명

100개 이하의 주어진 수 중 소수인 수의 개수를 구하는 문제

 

분류에 적혀있는 에라토스테네스의 체를 연습하기 위한 문제이다.

2 이상의 수 에 대하여 소수인 수의 곱 값은 소수가 아니다 라는 정의를 이용한다.

대표적인 소수 2를 기준으로 4, 6, 8, 은 2의 곱이므로 소수가 될 수 없다.

현재 탐색하는 수가 과거의 수들을 기준으로 곱으로 판정이 되지 않았다면 해당 수는 소수로 판별 할 수있다.

 

위키 백과 - 에라토스테네스의 체 : https://ko.wikipedia.org/wiki/에라토스테네스의_체

 

알고리즘

1. 1부터 1000까지 포함할 수 있는 배열을 생성한다.

2. 배열을 에라토스테네스의 체 함수를 통해 초기화한다.

 2 - 1. 0과 1은 소수가 아닌 것으로 설정한다.

 2 - 2. 2부터 500까지 현재 자신의 값이 소수로 판별 되면 1000 이하의 수 중 나머지가 0이되는 모든 수를 소수가 아닌 것으로 판별한다.

3. 수 x를 입력 받으면서 소수 판별 배열의 값이 false이면 결과값을 +1 한다.

4. 출력

 

소스코드

#include <iostream>

using namespace std;

const short MAX = 1000;

void eratos(bool arr[MAX + 1]) {

	arr[0] = arr[1] = true;
	for (int i = 2; i < MAX / 2 + 1; i++)
	{
		if (!arr[i])
		{
			for (int j = i * 2; j < MAX; j += i)
				arr[j] = true;
		}
	}
}

int main()
{
	int n;
	bool prime[MAX + 1] = {};
	int count = 0;
	
	eratos(prime);

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int k;

		cin >> k;

		if (!prime[k])
			count++;
	}

	cout << count;

	return 0;
}