(1978) 소수 찾기

https://www.acmicpc.net/problem/1978

단계별로 풀어보기

9단계(약수, 배수와 소수 1) 4번째

 

 

 

이것도 밀러-라빈 소수판별법 같은 게 있지만 일반적으로는 O(N)이나 O(√N)으로 충분하다.

 

 

 

#include <iostream>
using namespace std;

inline bool isprime(int x){
  if(x==1)  return false;
  
  for(int i=2;i<x;i++)  if(x%i==0)  return false;
  
  return true;
}

int main() {
  int n, ans= 0;
  
  cin >> n;
  
  while(n--){
    int x;
    
    cin >> x;
    
    if(isprime(x))  ans++;
  }
  
  cout << ans;
  
  return 0;
}