BOJ 1978번 :: 소수 찾기

#문제

#작성 코드

#include <iostream>
#include <stdio.h>

bool prime(int n){
	if( n<2 )
		return false;
	for(int i=2; i*i<=n; i++){
		if( n%i == 0 )
			return false;
	}
	return true;
}

int main()
{
	int N, cnt=0;
	// 수의 개수 입력 
	scanf("%d", &N);
	// N개만큼의 수 입력 
	int *arr = new int[N];
	for(int i=0; i<N; i++){
		std::cin>>arr[i];
	}
	
	// 소수 판별하기
	for(int i=0; i<N; i++){
		if(prime(arr[i]))
			cnt++;
	}
	printf("%d", cnt);
	return 0;
} 

##

2~sqrt(n) 범위 내에서 %연산을 통해 소수를 판별하면 2~n 범위에서 판별할때보다 계산량이 적어진다.

prime함수에서 n이 1일 경우를 빠트리지 않도록 주의!