Next Semiprime

View as PDF
Submit solution
Points: 10 (partial)
Time limit: 1.0s
Memory limit: 64M
Author:
EPICI
Problem type

Primes are no longer popular. Semiprimes are now trendy, and everyone wants one.

A semiprime is a number which has two prime factors, which do not need to be distinct. For example, the square of a prime is a semiprime.

The first few semiprimes are 4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33.

You have 1 \le Q \le 5 \cdot 10^4 friends you want to help out, numbered 1 \dots Q. Each friend has a number 1 \le N_k \le 10^9 where 1 \le k \le Q.

For each friend, you are to find the smallest semiprime strictly greater than N_k.

Constraints

Subtask Q N % of points
1 10 10^3 1
2 100 10^4 2
3 100 10^6 4
4 1\,000 10^8 8
5 10\,000 10^9 15
6 50\,000 10^9 70

Input Specification

The first line will contain Q. The next Q lines will contain all N.

Output Specification

The corresponding semiprime for each N, one per line.

Sample Input

7
1
5
100
1000000000
100
123456
987654321

Sample Output

4
6
106
1000000006
106
123458
987654343

Explanation

Factor and see for yourself.

Comments


  • 0
    andrewtam  commented on Oct. 18, 2020, 2:32 p.m. ← edited

    Is prime factorization the right approach to this question? Do I just need to further optimize my code or should I try something different?


  • 26
    Chensta  commented on Dec. 30, 2017, 12:41 a.m.

    I wish I had 50 thousand friends


    • 6
      Riolku  commented on April 2, 2019, 12:27 p.m.

      I wish I had 1.


      • 9
        HyperNeutrino  commented on April 2, 2019, 1:48 p.m.

        just do what I do and get some imaginary ones. then just multiply them by i and you'll have some friends :D


        • 9
          Zeyu  commented on April 2, 2019, 2:35 p.m.

          Wait doesn't that get you a negative amount of friends 😥


          • 11
            p1geon  commented on April 2, 2019, 6:52 p.m.

            multiply by i two more times! problem solved 😎