Bình luận

• 
  

  4

  

  dungdeptrai  đã bình luận lúc 17, Tháng 6, 2025, 13:06

  Nhiều lúc nghĩ học lập trình thật thú vị. Ở bài này, nếu dùng cách bthuong là viết 1 hàm isPrime duyệt từ 2 đến sqrt(n) rồi trong hàm main() duyệt từ a -> b, gặp số nào là số nguyên tố thì ++count. Nhưng chắc chắn là anh Lộc sẽ cho mình TLE ngay. Hôm bữa có học đc 1 trick trong lập trình thi đấu của anh kia. Sẽ vẫn dùng ý tưởng y chang trên, nhưng sẽ viết hàm isPrime khác đi 1 tý. Ý tưởng là: mọi số nguyên tố > 3 đều có dạng (6k + 1) hoặc (6k - 1). Độ phức tạp sẽ giảm đi 6 lần so với hàm isPrime cũ trên kia. Và nãy tôi thử thử AC full... :)) đỡ phải nghĩ nhiều đau đầu...

  Đây là code hàm isPrime đó:

  bool isPrime(int n) { if (n <= 1) return false; if (n <= 3) return true; if (n % 2 == 0 || n % 3 == 0) return false; for (int i = 5; i * i <= n; i += 6) { if (n % i == 0 || n % (i + 2) == 0) return false; } return true; }

• 
  

  0

  

  yuhpy  đã bình luận lúc 16, Tháng 7, 2025, 17:33 ← sửa 6 →

  cách này tôi coi trên YT cũng có 1 ông Ấn Độ nhắc đến nhưng nó không hoàn toàn đúng với mọi trường hợp. VD 25 = 6*4+1 mà 25 ko phải số nguyên tố. Vậy nên cũng ko thể chắc chắn 100% trong là các số nguyên tố đều có thể áp dụng phương pháp này =))) Nói chung là nếu đi thi thì cũng hên xui bộ test nữa.

  Tui đọc lại mới thấy n % i == 0 với i=5 n=25 của cái vòng for. (phương pháp khá hay 💯)

• 
  

  6

  

  Thai_Huy_Trietpbc  đã bình luận lúc 1, Tháng 7, 2025, 16:49

  t hay gọi là check nt nâng cao=))

• 
  

  1

  

  Phuc_ngu_3611  đã bình luận lúc 22, Tháng 6, 2025, 12:33

  cach nay rat thong minh

• 
  

  0

  

  bengokyeuanh99  đã bình luận lúc 11, Tháng 4, 2025, 8:47 ← chỉnh sửa →

  include <bits/stdc++.h>

  using namespace std; using ll = long long;

  vector<int> basePrimes(int limit) { vector<char> isPrime(limit + 1, true); isPrime[0] = isPrime[1] = false; for (int i = 2; i * i <= limit; i++) { if (isPrime[i]) { for (int j = i * i; j <= limit; j += i) isPrime[j] = false; } } vector<int> primes; primes.reserve(limit / 20); for (int i = 2; i <= limit; i++) if (isPrime[i]) primes.push_back(i); return primes; }

  int countTwinPrimes(ll a, ll b) { int limit = floor(sqrt(b)) + 1; vector<int> primes = basePrimes(limit); int size = b - a + 1; vector<uint8_t> isPrime(size, 1); if (a == 1) isPrime[0] = 0;

  for (auto p : primes) {
      ll start = max((ll)p * p, ((a + p - 1) / p) * p);
      if (start == p) start += p;
      for (ll j = start; j <= b; j += p) isPrime[j - a] = 0;
  }
  int count = 0;
  for (int i = 0; i + 2 < size; i++) {
      if (isPrime[i] && isPrime[i + 2]) count++;
  }
  return count;
  

  }

  int main() { ios::syncwithstdio(false); cin.tie(NULL); ll a, b; cin >> a >> b; cout << countTwinPrimes(a, b) << '\n'; }