pastebin

pastebin

Paste Search Dynamic
Recent pastes
vector is prime
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define NAME "sangnguyento"
  4. #define el cout<<"n"
  5. using namespace std;
  6.  
  7. void solve(){
  8.     ll n;
  9.     cin >> n;
  10.  
  11.     // Khởi tạo mảng kiểm tra số nguyên tố với kích thước là n/2
  12.     vector<bool> is_prime((n-1)/2 + 1, true);
  13.     for (int i = 0; i < is_prime.size(); ++i) {
  14.         is_prime[i] = true;
  15.     }
  16.  
  17.     // Duyệt các số lẻ để loại bỏ các số nguyên tố hợp số
  18.     for (int i = 3; i*i <= n; i += 2) {
  19.         if (is_prime[(i-1)/2]) {
  20.             for (int j = i*i; j <= n; j += 2*i) {
  21.                 is_prime[(j-1)/2] = false;
  22.             }
  23.         }
  24.     }
  25.  
  26.     ll count = 1;  // Đếm số nguyên tố 2
  27.     for (int i = 1; i < is_prime.size(); ++i) {
  28.         if (is_prime[i]) {
  29.             count++;
  30.         }
  31.     }
  32.     cout << count;
  33. }
  34.  
  35. int main(){
  36.     clock_t start = clock();
  37.     ios_base::sync_with_stdio(false);
  38.     cin.tie(null);
  39.     freopen(NAME".inp","r",stdin);
  40.     freopen(NAME".ans","w",stdout);
  41.     solve();
  42.     clock_t end = clock();
  43.     el;
  44.     double duration = (double)(end-start)/clocks_per_sec;
  45.     cout << "TIME 1: " << duration;
  46. }
  47.  
Parsed in 0.028 seconds