Hướng dẫn giải của Đếm số nguyên tố

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: tranxuantruong

Ý tưởng làm bài

  • Do A(i) bài này khá nhỏ chỉ có 1e6, nên ta dùng phương pháp sàng nguyên tố để lưu các số nguyên tố từ 1 tới 1e6
  • Tiếp đó là duyệt lại mảng A, nếu phần tử nào là số nguyên tố thì tăng đáp án lên 1
  • In đáp án ra màn hình

Code

#include <bits/stdc++.h>

using namespace std;

int main() {
   function <void(vector<int>&, int)>               //tìm từ khóa "con trỏ hàm" để hiểu cái này
   getSieve = [&](vector <int>& p, int sz){         //ta có thể viết hàm trực tiếp trong main(), giúp code liên tục, gắn kết
      p.resize(sz+1, true);                         //như 1 bài văn, giúp code dễ đọc hơn, dễ nhìn hơn và ít bị lỗi hơn
      p[0]=p[1]=false;                              //ngoài ra còn giúp không phải kéo lên kéo xuống nhiều khi đọc code, hay debug...

      for(int i=0, maxx=sqrt(sz)+1; i<maxx; ++i){
         if(!p[i]){
            continue;
         }

         for(int j=i*i; j<=sz; j+=i){
            p[j]=false;
         }
      }
   };

   vector <int> p;
   getSieve(p, 1e6);


   int n; cin >> n;

   vector <int> a(n);
   for(int i=0; i<n; ++i){
      cin >> a[i];
   }


   int ans=0;
   for(int i=0; i<n; ++i){
      if(p[a[i]]){
         ans+=1;
      }
   }

   cout <<ans <<endl;





   return 0;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.

Không có bình luận tại thời điểm này.