백준 1978번: 소수 찾기

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

1978번: 소수 찾기

 

 

 

 

문제

 

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

 

 

 

 

소수의 개수를 찾기 위해 에라토스테네스의 채를 사용한다. 

 

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>
#include <math.h>
using namespace std;

bool cn(int n){
	int m = sqrt(double(n));

	if(n == 1) return false;

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

	return true;
}

int main(void){
	int count;
	int n;
	int ans = 0; // 소수의 개수 저장

	cin>>count;
	for(int i = 0; i < count; i++)  {
		cin>>n;
		if(cn(n)) ans++;
	}

	cout<<ans;
}