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.
Input
The first line contains the number of test cases T. Each of the next T lines contains one integer n.
Output
Output T lines, containing the corresponding lucky number for that test case.
Constraints
1 <= T <= 20
1 <= n <= 1000
Example
Sample Input: 2 1 2 Sample Output: 30 42
hide comments
SangKuan:
2015-07-07 03:45:03
for who's answer for n = 1000 is 2988,there is at least three distinct prime factors,it is mean equal or bigger than three |
|
Dushyant Singh:
2015-06-05 19:10:00
Got it. :-) I was calculating for 3 distinct prime factors only i.e. not for number of distinct prime factors greater than 3. |
|
Ankush :
2015-06-05 08:55:01
Simple Brute Force and, used cin and cout. AC in 0.00 :P |
|
kshitij tripathi:
2015-06-03 20:51:20
Simple brute force 0.01 sec :) |
|
GAURAV CHANDEL:
2015-04-14 04:02:23
sieve can do many things... |
|
utkarsha gaumat:
2015-04-10 18:51:13
@Dushyant for n=1000 ans is 2664 |
|
Dushyant Singh:
2015-04-04 00:06:13
For n=1000 i am getting 2988 but in comments answer is different. Which one is correct? |
|
utkarsha gaumat:
2015-04-01 19:08:44
simple one |
|
Vaporeon:
2015-03-08 20:27:53
AC in 1st try.. :D precompute array containing lucky numbers.. (upto 3000 in enough).. |
|
Rajat (1307086):
2015-02-19 14:39:48
simply simple....:)
|
Added by: | Varun Jalan |
Date: | 2011-12-15 |
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 |