1978번: 소수 찾기 (BOJ C++)

1978번:  소수 찾기

사용 언어: C++

 

풀이

아래의 코드는 O(n)이지만, O(루트n)에 코드를 짤 수 있다. 해당 숫자의 루트 n까지만 확인하면 된다는 사실을 사용하는 것이다. 

for(int i=2; i*i<=num; i++)
{
	if(num % i == 0) 
    	flag = false;
}

하지만 귀찮으니 쓰진 않고 알아두기만 하자.

#include <iostream>
using namespace std;

int main(void)
{
	int num;
	int ans = 0;
	cin >> num;
	bool flag;
	while(num--)
	{
		int isPrime;
		flag = true;
		cin >> isPrime;
		if(isPrime == 1)
			continue;
		for(int i=2; i<isPrime; i++)
			if(isPrime % i == 0)
				flag = false;
		if(flag == true)
			ans++;
	}
	cout << ans << '\n';
	
	return 0;
}