Sphere Online Judge

Because of maintenance, it is currently impossible to submit any solutions. The maintenance will end around 3:00 am GMT (4:00 am SPOJ time).

This message will disappear once the maintenance is finished.

SPOJ Problem Set (classical)

1798. Assistance Required

Problem code: ASSIST

After the 1997/1998 Southwestern European Regional Contest (which was held in Ulm) a large contest party took place. The organization team invented a special mode of choosing those participants that were to assist with washing the dirty dishes. The contestants would line up in a queue, one behind the other. Each contestant got a number starting with 2 for the first one, 3 for the second one, 4 for the third one, and so on, consecutively.

The first contestant in the queue was asked for his number (which was 2). He was freed from the washing up and could party on, but every second contestant behind him had to go to the kitchen (those with numbers 4, 6, 8, etc). Then the next contestant in the remaining queue had to tell his number. He answered 3 and was freed from assisting, but every third contestant behind him was to help (those with numbers 9, 15, 21, etc). The next in the remaining queue had number 5 and was free, but every fifth contestant behind him was selected (those with numbers 19, 35, 49, etc). The next had number 7 and was free, but every seventh behind him had to assist, and so on.

Let us call the number of a contestant who does not need to assist with washing up a lucky number. Continuing the selection scheme, the lucky numbers are the ordered sequence 2, 3, 5, 7, 11, 13, 17, etc. Find out the lucky numbers to be prepared for the next contest party.

Input Specification

The input contains several test cases. Each test case consists of an integer n. You may assume that 1<=n<=3000. A zero follows the input for the last test case.

Output Specification

For each test case specified by n output on a single line the n-th lucky number.

Sample Input


Sample Output


Added by:Wanderley Guimar„es
Time limit:0.566s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel Pentium G860 3GHz)
Languages:All except: ERL JS
Resource:University of Ulm Local Contest 2003

hide comments
2014-03-06 07:21:21 AVOID
no need to calculate upto 4200 there 3000 sufficent to get AC:

Last edit: 2014-03-07 04:35:02
2013-12-24 14:43:35 raghvendra
done :) using doubly link list.........
2013-07-04 20:39:18 arjun
sieve with modifications
this is not a sequence of prime numbers
and for test case 20 ans is 83 :)
2013-06-28 12:39:25 Himanshu Sahu
easy one :)
2013-06-27 05:58:12 Nishant Gupta
@arman u r right ...no need to calculate beyond 3000 ....it's working upto 3000
2013-06-22 12:09:05 mystique_blue
@shagun try it on paper. it will get clearer. Explaining that means throwing the algorithm open. Sorry for that.
2013-06-22 12:03:46 mystique_blue
@sagar its working fine upto 3000 numbers....
@Shagun answer is 83 indeed.

@all carefully read the description. You are not simply printing the nth prime.... e.g output for 9 is a composite number!! :)
2013-06-01 09:04:13 anuj kumar jain
Don't use modulus function....it costed me 2 TLEs....

Last edit: 2013-06-01 09:04:36
2013-01-22 18:23:29 sagar bhavsar
the range given in wrong.....i calculated upto 4233 numbers and got accepted wile i was getting WA when i calculated upto just 3000

Last edit: 2013-01-22 18:23:51
2012-12-19 14:56:46 张翼德
remark - O(n^2) easily passes in C/C++ but for C#/java its not good enough :/
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.