[백준 1978] 소수 찾기

백준 1978번 소수 찾기 링크

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

1978번: 소수 찾기

 

 

소수를 판별할 수에 루트를 씌운 값이 약수의 중간값보다 살짝 크다는 것을 이용

이러면 시간 복잡도가 루트 n이다.

https://myjamong.tistory.com/139

소수(Prime Number) 구하기 효율적 알고리즘 :: 코드자몽

 

그리고 소수 판별 조건에 1은 소수가 아님을 추가한다. 참고 자료는

https://myjamong.tistory.com/139

소수(Prime Number) 구하기 효율적 알고리즘 :: 코드자몽

C++에서는 boolean이 아닌 bool 자료형을 사용한다.

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=pk3152&logNo=221561650139 

C++ (10) 자료형 bool (boolean 자료형)

 

그래서 내 풀이는

#include <iostream>

using namespace std;

bool isPrime(int num){

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

}

int main(void){
ios::sync_with_stdio(0);
cin.tie(0);

int cnt=0;

int n;
cin>>n;


for(int i=0; i<n; i++){
    int num;
    cin>>num;

    if(isPrime(num))
    cnt++;
}

cout<<cnt;

}