알고리즘 문제
[백준] 1978번 소수 찾기
feelcoding
2020. 1. 30. 19:21
728x90
1978번: 소수 찾기
첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.
www.acmicpc.net
자연수 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;
}
728x90