AMR11E - Distinct Primes

Arithmancy is Draco Malfoy's favorite subject, but what spoils it for him is that Hermione Granger is in his class, and she is better than him at it. Prime numbers are of mystical importance in Arithmancy, and Lucky Numbers even more so. Lucky Numbers are those positive integers that have at least three distinct prime factors; 30 and 42 are the first two. Malfoy's teacher has given them a positive integer n, and has asked them to find the n-th lucky number. Malfoy would like to beat Hermione at this exercise, so although he is an evil git, please help him, just this once. After all, the know-it-all Hermione does need a lesson.


The first line contains the number of test cases T. Each of the next T lines contains one integer n.


Output T lines, containing the corresponding lucky number for that test case.


1 <= T <= 20
1 <= n <= 1000


Sample Input:

Sample Output:

hide comments
phoemur: 2018-11-24 17:46:09

n <= 1000 makes it too easy to golf a solution

suyashky: 2018-11-08 19:48:15

AC 0.00
Used brute force to generate array of primes with >3 ( NOTE THIS ! ) prime factors. and printed (i-1)th term of array.

gam_hpang1812: 2018-07-01 07:23:47

what is 1000th lucky number?

aadichai22: 2018-06-02 13:35:54

Ac in 2nd attempt.

coderslegacy: 2018-04-21 02:28:58

just use simple sieve and genrate look up table

coding_panda: 2018-04-05 08:24:23

AC 0.0 using Sieve :D

prashant_pc: 2018-03-01 13:48:37

Used sieve first to store prime numbers in array ..used the array to find the prime factors

Last edit: 2018-03-19 09:24:02
a_98: 2018-02-01 13:16:52

A.C. 0.02
No Siev.
used sqrt func.

Last edit: 2018-02-01 13:17:56
nishant_26: 2018-01-16 15:01:13

easy! AC in one go

jayharsh: 2017-08-11 19:07:56

AC in one Go 0.03 Sec!

Added by:Varun Jalan
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Varun Jalan - ICPC Asia regionals, Amritapuri 2011