SPOJ.com - Problem NAJPLNP

NAJPLNP - Prime Land and Next Prime number

Prime land is a famous city of Wonderland. In primeland most of the people are mathematician. They are very much interest in Prime number. Prime number are those number which only divisible by 1 and Own. So 1 is not a prime number. They know all the prime generate theory of Eratosthenes, Pythagoras, Fermat, Diophantus, Furko, Gauss and so on. However, his favorite one is Euler. The only thing Witua likes more than Euler is Euler’s totient function φ. But with those theory the can generate only 16th digit prime. Now They want to generated more digit prime number.

Using those theory I know you can generate 18 digit (less than 10^18) prime number which is satisfy the primeland people. So please Help the primeland people.

Given a long integer number. You should print the next prime number. If he given number is prime just print it. It is satisfy that all the given Integer have a next prime under 10^18.

Input:

Input starts with an integer T (≤ 1000), denoting the number of test cases. Next line given a positive Integer Number N. 0 ≤ N ≤ 10^18

Output:

For each test case, print the case number and the next prime number.

Sample:

Input	Output
6 1 2 10 20 100 1000000	Case 1: 2 Case 2: 2 Case 3: 11 Case 4: 23 Case 5: 101 Case 6: 1000003

Submit solution!

Added by:	Najmuzzaman
Date:	2014-10-25
Time limit:	0.5s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64

hide comments

2014-10-27 11:25:45 Najmuzzaman
@Francky Thank. I am waiting for your Strong Dataset.

Actually i can not find out any tricky case. And I generate the data set using random function.

Again Thanks for taking a step to generate data set.

--ans(Francky)--> Data in construction... For those who are impatient, I recommend Prime Again ; my problem will be a 64bit edition.

--ans (Najmuzzman) --> That will be great. If your problem udpate to 64 bit.

Last edit: 2014-10-28 14:23:33

2014-10-26 20:40:44 [Lakshman]
Agree with Francky, Test cases are too weak. It will be a nice and challenging task if Franky will set a similar problem.

2014-10-26 19:23:32 Najmuzzaman
@Francky Now Can i put it in Classic.
--ans(Francky)--> Sorry, but I've started a generation of serious strong input files (I really know how to do that). I take the ball to make a problem that will 'repair' the change pyramid->cube for PON ; there were before very few AC at 0.00s. You problem is a good tutorial one ; please let it in place.
Please keep in mind that a problem should be fully ready at time of publication, we don't like too many changes, when it's possible. Thanks for your comprehension.

Last edit: 2014-10-26 20:09:42

2014-10-26 19:23:32 Francky
Moved to tutorial.
@psetter : please check in spoj problem set database if "your" problem already exists or not, or make sure the constraints are very different. Moreover here, it is need to build a very serious (strong) input file, with some various strong pseudo-primes.

2014-10-26 19:23:32 [Lakshman]
Its too easy should be in tutorial.If problem setter want to put this for classical then number of test cases should be increased to 1000.

2014-10-26 19:23:32 Francky
There's yet NOVICE24 and AU12, ...
I don't think this one should stay in classical, too weak. Any other comments about that ?

2014-10-26 19:23:32 fitcat
It is contradictory that "Next line given a positive Integer Number N. 0≤N≤10^18." I treated N as positive integer and caused me 2 WA!