자료구조 및 알고리즘/백준
[백준 1978] 소수 찾기
아기사우르스
2023. 4. 1. 23:37
728x90
백준 1978번 소수 찾기 링크
https://www.acmicpc.net/problem/1978
소수를 판별할 수에 루트를 씌운 값이 약수의 중간값보다 살짝 크다는 것을 이용
이러면 시간 복잡도가 루트 n이다.
https://myjamong.tistory.com/139
그리고 소수 판별 조건에 1은 소수가 아님을 추가한다. 참고 자료는
https://myjamong.tistory.com/139
C++에서는 boolean이 아닌 bool 자료형을 사용한다.
https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=pk3152&logNo=221561650139
그래서 내 풀이는
#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;
}
728x90