[BOJ] 1978 소수 찾기

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

Note

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

분류에 적혀있는 에라토스테네스의 체를 연습하기 위한 문제이다.
2 이상의 수 에 대하여 소수인 수의 곱 값은 소수가 아니다 라는 정의를 이용한다.
대표적인 소수 2를 기준으로 4, 6, 8, 은 2의 곱이므로 소수가 될 수 없다.
현재 탐색하는 수가 과거의 수들을 기준으로 곱으로 판정이 되지 않았다면 해당 수는 소수로 판별 할 수있다.

위키 백과 - 에라토스테네스의 체

알고리즘

1. 1부터 1000까지 포함할 수 있는 배열을 생성한다.
2. 배열을 에라토스테네스의 체 함수를 통해 초기화한다.
   1. 0과 1은 소수가 아닌 것으로 설정한다.
   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;
}

2019-01-21 10:00:00에 Tistory에서 작성되었습니다.