[Lý Thuyết Số - Toán Học]. Bài 95. Số nguyên tố sinh đôi

View as PDF
Submit solution
Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Problem source:
28Tech
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

28Tech gọi 2 số x và x + 2 là 2 số nguyên tố sinh đôi nếu cả 2 số này đều là số nguyên tố, bạn hãy giúp 28Tech đếm số lượng cặp số nguyên tố sinh đôi trong khoảng 2 số a, b.

Lưu ý là cặp số (x, y) sẽ được coi là giống cặp số (y, x)

Đầu vào
  • Dòng duy nhất chứa 2 số a, b
Giới hạn

  • 1≤a≤b≤10^9

  • b-a≤10^6

Đầu ra
  • In ra đáp án của bài toán

Ví dụ :

Input 01
3 13
Output 01
3
Giải thích test :
Các cặp thỏa mãn là (3, 5), (5, 7) và (11, 13)

Comments

Please read the guidelines before commenting.


  • 0
    zXCczxvzxv  commented on Jan. 21, 2026, 12:52 p.m.

    mmb


  • 0
    khanhbitchoi205  commented on Jan. 9, 2026, 4:18 p.m.

    bai kho qua huhu


  • 0
    Ngo_Truong777  commented on Jan. 6, 2026, 2:37 p.m.

    .


  • 0
    Ngo_Truong777  commented on Jan. 6, 2026, 2:34 p.m.

    .


  • 0
    iamdumb1234  commented on Nov. 9, 2025, 6:17 a.m.

    Bài này dùng sàng ngto ko đc à mn?


  • 0
    Van_dinh_211  commented on Oct. 17, 2025, 8:29 a.m.

    include<bits/stdc++.h>

    using namespace std; bool checknt(long long n) { for(int i=2;i<=sqrt(n);i++) if(n%i==0) return false; return true; } int main() { int dem=0; long long a,b; cin>>a>>b; for(int i=a;i<=b;i++) { if(checknt(i)==true&&checknt(i+2)==true) dem++; }cout<<dem; } sao code mình ko full đc ac v mn :))


  • 4
    dungdeptrai  commented on June 17, 2025, 1:06 p.m.

    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  commented on July 16, 2025, 5:33 p.m. ← edit 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 💯)


      • 0
        minhkhang2113  commented on Oct. 9, 2025, 3:09 p.m.

        6k+1 hoặc 6k-1 mà b, k=4 thì 6k+1 không thỏa nhưng 6k-1 thỏa


    • 6
      Thai_Huy_Trietpbc  commented on July 1, 2025, 4:49 p.m.

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


    • 1
      Phuc_ngu_3611  commented on June 22, 2025, 12:33 p.m.

      cach nay rat thong minh


  • -4
    bengokyeuanh99  commented on April 11, 2025, 8:47 a.m. ← edited

    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'; }