Sàng Eratosthenes

Submit solution
Points: 3
Time limit: 1.0s
Memory limit: 98M
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Cho hai số nguyên dương L ≤ R. Hãy đếm xem trong đoạn [L, R] có bao nhiêu số nguyên tố.

Input:

  • Dòng đầu ghi số nguyên dương T là số bộ test. (T < 10^3)
  • T dòng tiếp theo, mỗi dòng chứa hai số nguyên dương L, R cách nhau bởi một dấu cách. \((1 < L \le R \le 10^6)\)

Output:

  • Với mỗi cặp số L và R, ghi ra trên một dòng số số nguyên tố trong đoạn [L, R]. (Đoạn [L, R] ít hơn \(10^6\) phần tử)

Example: Input1:

2
2 3
10 15

Output1:

2
2

Input2:

3
10 12
5 10
7 25

Output2:

1
2
6

Comments


  • 3
    TICHPX  commented on April 28, 2024, 9:58 a.m.

    Mời anh em thao khảo video của Tichpx

    https://www.youtube.com/watch?v=pUefyTF5Ucg


  • 0
    ga123  commented on Sept. 5, 2021, 12:37 p.m. ← edit 3

    Mình đã giải thích nguyên lý chạy của thuật toán ở bên dưới, code này là của phần thuật toán sàng đoạn giữa hai số, nếu bạn muốn dùng thì phải tự đọc hiểu và chế biến theo yêu cầu đề bài. chú ý là mĩnh đã nói rõ: thuật toán này chỉ lọc các số đến trước nố ,nếu bản thân đầu vào là 1 số nguyên tố thì sẽ không được tính, nên phải +1 vào đầu vào thuật toán.

    unsigned long SieveOfEratosthenes(unsigned long n,unsigned long n2
{

    unsigned long dem=0;
    bool prime[n2+1];
    bool prime2[n2+1];
    memset(prime, true, sizeof(prime));//gia su toan bo mang la so nguyen to
    memset(prime2, true, sizeof(prime));//gia su toan bo mang la so nguyen to
    for(unsigned long p=2;p*p<=n2;p++)//cho so nguyen bat ky chay tu 2 den can bac hai cua n
    {
        if (prime[p]==true)//neu gia tri la true, tiep tuc kiem tra
        {
            for (unsigned long i=p*p;i<=n2;i+=p)
                {
                prime[i]=false;
                }
        }
    }
    for(unsigned long p=n+1;p<n2;p++)
    {
        prime[p]=false;//lọc các thành phần bé hơn n2 và to hơn n. mình để n+1 vì số nào đằng sau n thì cũng không đc coi là nguyên tố trong mảng của n. như vậy khi so sánh thì chỉ có mảng của n2 là true sau khi qua vị trí n.
    }    
    for(unsigned long p=2;p*p<=n2;p++)//cho so nguyen bat ky chay tu 2 den can bac hai cua n
    {
        if (prime2[p]==true)//neu gia tri la true, tiep tuc kiem tra
        {
            for (unsigned long i=p*p;i<=n2;i+=p)
                prime2[i]=false;
        }
    }

    for (unsigned long p = 2; p <= n2; p++)
        if (prime2[p]==true&&prime[p]==false)
        dem++;
    return dem;
}

  • 0
    ga123  commented on Sept. 4, 2021, 9:47 a.m.

    ai giải thích cho mình vì sao sàng eratothenes lại nhanh hơn cách làm bth đc không


  • 0
    ga123  commented on Sept. 4, 2021, 8:56 a.m.

    sàng eratosthosnos có vẻ rất khó hiểu, nên mình để lại ở đây vài ghi chú đề phòng quên.

    Ý tưởng chủ đạo của sàng erothosnos cũng giống như các bài toán thông thường dùng để tìm số chia hết , vì vậy nó rất đơn giản để hiểu , giới hạn tính toán của máy tính là 3 đển 5x10^7 một giây, nên thuật toán sàng có thể tính đến mức 10 triệu trong vòng chưa đến 1s. đầu tiên, ta giả sử toàn bộ số đầu vào là số nguyên tố.

    ta xét từ i=1 đến căn bậc hai của n ,vậy số m trong danh sách ban đầu có vị trí có thứ tự i bình phương sẽ không thể là số nguyên tố. tiếp đó, các điểm cách đều từ điểm m với khoảng cách là i cũng sẽ không thể là số nguyên tố, vì 2*2+2 +2 =8 không phải là số nguyên tố. lọc từ đây cho đến hết danh sách sẽ tìm được toàn bộ số nguyên tố.

    điểm yếu của thuật toán là trong trường hợp số đầu tiên hoặc cuối là số nguyên tố , vì thuât toán chỉ đọc từ số sau trở đi, và dừng trước số cuối

    để giải quyết thì chúng ta chỉ cần đẩy được vị trí đầu thành vị trí đầu trừ 1 , vị trí cuối +1 .


  • 0
    TICHPX  commented on Aug. 20, 2021, 11:20 a.m.

    Có test nào L=1e9-1e5, R=1e9 chưa nhỉ


    • 0
      kai  commented on Aug. 20, 2021, 12:47 p.m.

      E chưa có ạ :(


  • 0
    kai  commented on Aug. 19, 2021, 2:44 p.m.

    Xin lỗi các bạn :(( Bộ test mình có vấn đề nhưng mình sửa lại và chấm lại bài cho các bạn rồi!!