[백준] 1978번 소수 찾기

1978번: 소수 찾기

자연수 n이 주어졌을 때 n이 소수인지 아닌지 알아보려면 어떻게 해야 할까?

2부터 n-1까지 n을 나눠보면 된다.

하지만 다시 잘 생각해보면 굳이 n-1까지 가지 않아도 알 수 있다.

n / 2까지만 나눠보면 소수인지 아닌지 판별이 가능하다.

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

int main() {
	int n;
	cin >> n;
	int* numbers = new int[n];
	for (int i = 0; i < n; i++) {
		cin >> numbers[i];
	}
	int count = 0;
	for (int i = 0; i < n; i++) {
		if (numbers[i] == 1) {
		}
		else if (numbers[i] == 2) {
			count++;
		}
		else {
			bool flag = false;
			for (int j = 2; j <= numbers[i] / 2; j++) {
				if (numbers[i] % j == 0) {
					flag = true;
					break;
				}
			}
			if (!flag) count++;
		}
	}
	cout << count;
	return 0;
}