[1978] 백준 : 소수 찾기(C++)

 

* 접근 방법
- 예전에 프로그래머스?에서 비슷한 문제를 본 적이 있어서 '에라토스테네스의 체'를 생각해 냄
- 수의 범위인 1000이하의 배열을 생성해둔 다음 0으로 초기화 함
- 1은 소수가 아니므로 1로 바꿔주고 2부터 반복문을 돌림
- 2가 소수면, 2*2, 2*2 + 2, 2*2 +2 +2 ... 은 소수가 아니므로 1로 바꿔줌
- 반복문 i의 조건은 i*i<=1000이 되는 것을 알 수 있음
  즉, 1~n 구간의 소수를 찾고 싶은 경우, t^2>n을 만족하는 t보다 작은 배수만 지워도 됨
       ex) 1~120이면, 11^2>120 이므로, 11보다 작은 수 배수들만 처리해주면 됨

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	vector<int> num(1001, 0);
	int answer = 0;
	int T = 0;
	cin >> T;

	num[1] = 1;
	for (int i = 2; i*i <= 1000; i++)
	{
		if (num[i] == 0)
			for (int j = i * i; j <= 1000; j += i)
				num[j] = 1;
	}

	for (int i = 0; i < T; i++)
	{
		int a = 0;
		cin >> a;
		if (num[a] == 0) answer++;
	}
	cout << answer;
	return 0;
}

 

- 문제에 주어진 조건을 잘 보자.. 100과 1000을 헷갈리다니..