# Lời giải bài đếm số nguyên tố trong dãy

###### 📌 Tags: `Sieving` ,`Math` .
____
## Ý tưởng :+1:
* Đầu tiên ta cần nhận biết cách để kiểm tra một số có phải là số nguyên tố hay không ?
* Với rất nhiều cách kiểm tra số nguyên tố thì ta phải chọn cách nào là phù hợp nhất ?
___
## Các thuật toán kiểm tra số nguyên tố
Ta có thể tham khảo ở [đây](https://vnoi.info/wiki/translate/he/Number-Theory-2.md)
____
## Nhận xét :bulb:
* Bài này có $n$ $\le$ $10^{5}$ nên không thể dùng hai thuật toán đầu như link trên
* Và dữ kiện quan trọng là $a[i]$ $\le$ $10^{6}$ vừa hay lại phù hợp cách dùng của thuật toán sàng nên suy ra bài này .Đầu tiên ta phải sàng nguyên tố rồi sau đó chạy for từ $1->n$ để kiểm tra $a[i]$ có phải là số nguyên tố hay không , nếu có thì cập nhật biến kết quả lên $1$
____
## Code
> **Time:** $O(10^{6} \log 10^{6})$
> **Space:** $O(n )$
> **Algo:** Sieveing .
> [color=lightgreen]
:::success
:::spoiler code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = 1e18 + 7;
const ll MAXN = 1e6 + 7;
bool nt[MAXN];
int n , a[MAXN] , d = 0;
void sangnt(){
    nt[0] = true;
    nt[1] = true;
    for(int i = 2 ; i * i <= MAXN - 7 ; i ++){
         if(!nt[i]){
            for(int j = i * i ; j <= MAXN - 7 ; j += i ){
                nt[j] = true;
            }
         }
    }
 
}
int main(){
   freopen("CNUMPRIM.inp" , "r" , stdin);
   freopen("CNUMPRIM.out" , "w" , stdout);
   cin >> n ;
   for(int i = 1 ; i <= n ; i ++){
       cin >> a[i];
   }
   sangnt();
   for(int i = 1 ; i <= n ; i ++){
       if(!nt[a[i]]){
           d ++;
       }
   }
   cout << d;
   return 0;
}

:::success
:::::