Lại là số nguyên tố

Xem dạng PDF
Gửi bài giải
Điểm: 0,29 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Tìm số nguyên tố gần nhất nhỏ hơn ~N~ ~\left(3 \leq N \leq 2^{32}\right)~.

Input

Dòng đầu tiên chứa số nguyên ~T~ là số lượng test ~\left(T \leq 10000\right)~

~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~N~.

Output

Với mỗi test, in kết quả trên một dòng.

Sample Input

3
5
10
17

Sample Output

3
7
13

Bình luận

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


  • 0
    duongoi281012  đã bình luận lúc 13, Tháng 12, 2025, 19:01 ← sửa 5

    không dùng sàng hay fermat SPOIL

    #include <bits/stdc++.h>
#define ll long long
#define faster ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int maxp = 65536;
bool a[maxp];
int snt;
int dem = 0;
void sieve()
{
    for(int i = 2; i * 1ll *  i <= maxp; i++)
    {
        if(!a[i])
        {
            for(int j = i * i; j <= maxp; j += i) a[j] = 1;
        }
    }
    for(int i = 2; i <= maxp; i++)
    {
        if(!a[i])
        {
            if(i % 2 != 0 || i == 2) snt[++dem] = i;
        }
    }
}

bool isprime(ll n)
{
    if(n < 2) return 0;
    if(n == 2) return 1;
    if(n % 2 == 0) return 0;
    for(int i = 1; i <= dem; i++)
    {
        ll p = snt[i];
        if(p * p > n) break;
        if(n % p == 0) return 0;
    }
    return 1;
}

int main()
{
    faster;
    sieve();
    int t;
    cin >> t;
    while(t--)
    {
        ll n;
        cin >> n;
        ll x = n - 1;
        if(n <= 2) {cout << 3 << '\n'; continue;}
        if(n == 3) {cout << 3 << '\n'; continue;}
        if(x % 2 == 0) x--;
        while(!isprime(x)) x -= 2;
        cout << x<< '\n';
    }
}

  • 1
    NVTai  đã bình luận lúc 3, Tháng 4, 2025, 14:56 ← chỉnh sửa

    :)))khoai thiệt chứ, submit gần 20 lần ms ac


  • 7
    YougiTuber  đã bình luận lúc 16, Tháng 1, 2025, 6:02 ← chỉnh sửa

    Spoil ⚠️

    Khoảng cách lớn nhất giữa ~2~ số nguyên tố nhỏ hơn ~2^{32}~ là không quá lớn, có thể duyệt trâu để thử (~2~ số cách nhau lớn nhất khoảng ~336~)

    Có thể dùng một thuật kiểm tra số nguyên tố nào đó (Fermat nhỏ hoặc Miller - Rabin) để đạt được thuật toán có độ phức tạp khoảng ~O(t.log(n)^2*336)~.

    Lưu ý:

    Vì ~n \le 2^{32}~ nên cần để kiểu dữ liệu unsigned long long tránh tràn số ở phép nhân.


  • 1
    nn9450898  đã bình luận lúc 19, Tháng 11, 2024, 13:06

    ,


  • -7
    ThanhBC1234  đã bình luận lúc 1, Tháng 10, 2024, 1:22

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -8
    duongajaas12  đã bình luận lúc 11, Tháng 4, 2024, 14:46 ← chỉnh sửa

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -29
    kaksaki1234  đã bình luận lúc 24, Tháng 8, 2022, 15:37

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.