Số nguyên tố!

View as PDF
Submit solution
Points: 0.07 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho ~2~ số nguyên ~N~ và ~K~ ~\left(1 \leq N \leq 2^{64} - 1;\text{ } 3 \leq K \leq 10\right)~. Tìm số nguyên lớn nhất không vượt quá ~N~ và là tích của ~K~ số nguyên tố liên tiếp.

Input

  • Dòng đầu là số nguyên ~T~ tương ứng với số bộ test ~\left(1 \leq T \leq 15\right)~.
  • ~T~ dòng tiếp theo mỗi dòng là ~1~ cặp số ~\left(N, K\right)~ cách nhau ~1~ dấu cách.

Output

  • Gồm ~T~ dòng là kết quả của ~T~ bộ test tương ứng, nếu không tìm được số thỏa mãn in ra ~-1~.

Sample Input

2
100 4
110 3

Sample Output

-1
105

Comments

Please read the guidelines before commenting.


  • 0
    Thien2009  commented on April 23, 2026, 8:00 a.m.

    mắt không thấy 3 <= k


  • -5
    thieen  commented on Aug. 19, 2025, 11:59 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 1
    THPTHD_Hieu  commented on May 12, 2025, 12:01 p.m.

    bài quỷ nha ae


    • -6
      RussVN123  commented on May 13, 2025, 6:39 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


    • 0
      anle82917  commented on May 12, 2025, 12:39 p.m. ← edit 4

      bài không quỷ đâu đối thủ hsg tỉnh sóc trăng !!! gợi ý :

      vì nó là k số nguyên tố liên tiếp nên ta luôn có đáp án là x1.x2.x3...xk >= x1^k (x1<x2<..<xk là các số nguyên tố >! liên tiếp ) đáp án sẽ lớn hơn x1^k . với x1 là số nhỏ nhất , N>=10^18 (xét k=3 , x1<=10^6 . k=4 x1<=10^4.5 , ... x1<=căn bậc k >! của N) vậy chỉ cần xét các số nguyên tố <=10^6 và 14 số đầu tiên >=10^6 là đủ . chặt nhị phân , sàng nguyên tố !!! Ngoài ra nên có cách tránh tràn số (log10 2 vế)


      • -5
        THPTHD_Hieu  commented on May 28, 2025, 2:56 p.m.

        This comment is hidden due to too much negative feedback. Show it anyway.


        • -6
          anle82917  commented on May 28, 2025, 4:25 p.m.

          This comment is hidden due to too much negative feedback. Show it anyway.


          • -5
            THPTHD_Hieu  commented on May 29, 2025, 1:46 p.m.

            This comment is hidden due to too much negative feedback. Show it anyway.


      • -6
        THPTHD_Hieu  commented on May 28, 2025, 2:38 p.m.

        This comment is hidden due to too much negative feedback. Show it anyway.


        • -7
          RussVN123  commented on May 28, 2025, 3:01 p.m.

          This comment is hidden due to too much negative feedback. Show it anyway.


          • -5
            THPTHD_Hieu  commented on May 29, 2025, 1:46 p.m.

            This comment is hidden due to too much negative feedback. Show it anyway.


        • -6
          RussVN123  commented on May 28, 2025, 3:01 p.m.

          This comment is hidden due to too much negative feedback. Show it anyway.


          • -5
            THPTHD_Hieu  commented on May 29, 2025, 1:46 p.m.

            This comment is hidden due to too much negative feedback. Show it anyway.


  • -5
    THPTHD_Hieu  commented on May 11, 2025, 1:57 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -37
    sunshine262  commented on July 23, 2024, 8:25 a.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.