[1978]소수 찾기 - C++

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

 

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

 

출력

주어진 수들 중 소수의 개수를 출력한다.

 

풀이:

그냥 브루트 포스로 풀면 되기야 하지만 그러면 메모리 초과날까 싶어서 아리스토텔레스의 체를 사용하였다.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

#include<iostream>

bool array[1001]; //1000으로 명시되어 있었으므로 

int main(){
	for(int i = 0;i < 1001;i++)	array[i] = true;
	array[0] = false; //0과 1은 모두 소수가 아니므로 
	array[1] = false; //false로 명시해 놓는다. 
	for(int i = 2;i < 32;i++){ // 1001의 제곱근이 31.6... 이므로 그냥 32로 지정하였다. 
		if(array[i]){
			int count = i;
			while(count <= 1001){
				count += i;
				array[count] = false;
			}
		}
	}
	int n, count = 0,input;
	std::cin>>n;
	for(int i = 0;i < n;i++){
		std::cin>>input;
		if(array[input]) count++;
	}
	std::cout<<count;
	
	
}

사실 이거는 프로그래밍 실력을 키우기 보다 수학문제다 보니까 별생각이 없다.