Next Semiprime

View as PDF

Submit solution

All submissions

Best submissions

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$ $4$ , $6$ $6$ , $9$ $9$ , $10$ $10$ , $14$ $14$ , $15$ $15$ , $21$ $21$ , $22$ $22$ , $25$ $25$ , $26$ $26$ , $33$ $33$ .

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

For each friend, you are to find the smallest semiprime strictly greater than $N_k$ $N_{k}$ .

Constraints

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

Input Specification

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

Output Specification

The corresponding semiprime for each $N$ $N$ , one per line.

Sample Input

Copy

Sample Output

Copy

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 😎

8

Plasmatic commented on April 3, 2019, 12:55 p.m. ← edited →