Next Prime

View as PDF

Submit solution

All submissions

Best submissions

Points: 5

Time limit: 2.0s

Memory limit: 64M

Problem type

Brute Force Practice 3

You love prime numbers. You own a number, but you suspect it might not be prime. You want a prime number, but it must be at least as large as the number you currently own. Find the smallest number that satisfies those conditions.

Input Specification

The first line will have the integer $N$ ~N~ $(1 \le N \le 2 \times 10^9)$ ~(1 \le N \le 2 \times 10^9)~.

Output Specification

Print the number you want.

Sample Input

Sample Output

Comments

-3

vladlen044 commented on Sept. 25, 2022, 5:08 p.m.

Didn't read input specs carefully enough, it got me good

3

Blackgaurdian3 commented on July 17, 2020, 1:43 p.m.

I keep on getting TLE for the last few cases. I can't think of a faster way to do this problem using Python3.

I tried Wilson's Theorem but apparently that's too slow as well?

Any tips

0

20220680 commented on Sept. 21, 2022, 1:42 a.m. ← edited →

HINT: There's a conclusion that for any positive integer $a$ ~a~, there must be a prime in the range of $a, 2a$ ~a, 2a~ (I got this on google)

0

20220680 commented on Sept. 21, 2022, 1:41 a.m. ← edited →

Actually when I was collecting interesting facts about prime numbers when doing my Math culminating work last semester, I found a conclusion that for any integer $a$ ~a~, there must be a prime number within the range of $a, 2a$ ~a, 2a~, and this may help you (And I finally passed this problem by using this property)

13

sa35577 commented on July 17, 2020, 3:08 p.m. ← edit 2 →

Your first approach is much better and can be fixed by just adding one thing (https://dmoj.ca/src/2209547).

Ask yourself this: do you need to check all the numbers up to $N$ ~N~ to determine whether or not it is prime?

2

Juniboy03 commented on Feb. 23, 2019, 3:24 a.m.

Does anyone know how to make my program run faster?

4

billbai0102 commented on March 12, 2020, 2:56 a.m. ← edited →

If you're using Java, you can use the BigInteger class because it has the method isProbablyPrime(), which checks if it's a prime pretty fast. I just incremented by 2 each time and checked if the resulting number is prime to get the next prime.

3

sushi commented on March 12, 2020, 2:14 p.m. ← edited →

Yes, because that uses the miller-rabin primality test, which is $\mathcal{O}(k \log^3 N)$ ~\mathcal{O}(k \log^3 N)~ time on average, where $k$ ~k~ is the number of times the test is performed, which is generally a small constant number.

4

magicalsoup commented on Feb. 23, 2019, 3:34 a.m.

I suggest you read the comments

-45

alexzhang commented on June 28, 2018, 12:44 a.m.

I always thought one was a prime number.....

This comment is hidden due to too much negative feedback. Show it anyway.

-3

QiQi commented on Dec. 3, 2021, 3:40 a.m.

The link didn't work for me but I know the answer, a number is prime if it has two factors and the only factor of one is 1 X 1.

-14

nishux commented on Nov. 15, 2017, 12:19 a.m. ← edited →

There seems to be a problem with test case #2 and #6 when I run my code. Can someone please check my test cases.

This comment is hidden due to too much negative feedback. Show it anyway.

23

injust commented on Nov. 16, 2017, 4:21 a.m.

Instead of suggesting that correct solutions from 400+ other users are flawed, you may want to take another look at the problem statement (emphasis mine):

You want a prime number, but it must be at least as large as the number you currently own.

-36

PhatBallllz commented on Feb. 26, 2020, 5:49 a.m.

There seems to be a problem with the testing. I know my code is correct. Not sure why this has happened. Please fix the site thanks.

This comment is hidden due to too much negative feedback. Show it anyway.

8

Bobbychuck12 commented on July 18, 2021, 3:04 p.m.

There seems to be a problem with your code. I know the site is correct. Not sure why this has happened. Please fix your code thanks.

38

nishux commented on Nov. 28, 2017, 9:16 p.m.

Didn't mean to say that the test cases were wrong. I just didn't know what was wrong with my code.Sorry for the miscommunication.

-2

John commented on Oct. 5, 2022, 5:22 p.m.

You know edits are visible to everyone, right?

-35

Anix55 commented on Oct. 16, 2015, 12:31 a.m.

what does TLE mean?

This comment is hidden due to too much negative feedback. Show it anyway.

3

lele commented on Jan. 26, 2019, 11:44 p.m.

Time Limit Exceeded

12

Xyene commented on Oct. 16, 2015, 12:37 a.m.

It means your program has exceeded the per-testcase time limit (in this case, 2 seconds). You can hover over status codes, as their alt text provides more details on what they are.

-18

bobhob314 commented on Jan. 6, 2015, 10:08 p.m.

Are there any pointers you could give me to solve this question? Should I use the Sieve or something? I'm stuck :(

This comment is hidden due to too much negative feedback. Show it anyway.

6

FatalEagle commented on Jan. 6, 2015, 10:55 p.m.

The name of the problem might give a hint. Specifically, "Brute Force Practice 3".

4

FatalEagle commented on Nov. 14, 2014, 7:29 p.m.

Even though this is Brute Force Practice 3, you still need a little optimization -- for example, can you determine if a number is prime just by checking divisors up to and including the square root of a number?

-19

omaewamoushindeiru commented on Nov. 14, 2014, 8:34 a.m.

Keep getting 90%, first test fails. What...

This comment is hidden due to too much negative feedback. Show it anyway.

3

FatalEagle commented on Nov. 14, 2014, 4:27 p.m.

Partial output has been enabled. You can see what output your program produced (up to about 32 bytes for now) and try to debug your code.

-17

PaulOlteanu commented on Nov. 25, 2014, 3:06 a.m.

Has the output been disabled?

This comment is hidden due to too much negative feedback. Show it anyway.

-18

PaulOlteanu commented on Nov. 25, 2014, 3:08 a.m.

Nevermind. It seems the output only displays if you have less than a certain number of mistakes.

This comment is hidden due to too much negative feedback. Show it anyway.

5

FatalEagle commented on Nov. 25, 2014, 3:51 a.m.

Actually, there will not be an arrow if your program does not produce any output. That was what was really happening.

-18

Yuting9 commented on Oct. 28, 2014, 12:47 a.m.

I can't seem to get the last test to work for my code...

This comment is hidden due to too much negative feedback. Show it anyway.

5

FatalEagle commented on Oct. 28, 2014, 1:13 a.m.

Your code is incorrect. There is a corner case you missed.

-16

Yuting9 commented on Oct. 28, 2014, 1:59 a.m.

what do you mean, "corner case?"

This comment is hidden due to too much negative feedback. Show it anyway.

5

FatalEagle commented on Oct. 28, 2014, 2:01 a.m.

If I wrote it here, it wouldn't be a corner case anymore. Make sure your solution is valid for all possible inputs within the range specified.

-6

JannyWang commented on Oct. 17, 2014, 1:28 a.m.

Does it have to work for decimals?

This comment is hidden due to too much negative feedback. Show it anyway.

2

quantum commented on Oct. 17, 2014, 3:32 a.m.

Inputs are integer only.

5

quantum commented on Sept. 28, 2014, 1:59 a.m.

Not fair how /^1?$|^(11+?)\1+$/ fails.

-1

simohamedd commented on May 5, 2018, 8:51 a.m. ← edited →

it fails because

public class Piggy {public static int nextPrime(int n) {System.out.println(nextPrime(n));} return %$a++;

36

FatalEagle commented on Sept. 28, 2014, 3:43 a.m.

If only the memory limit was a few GB more and you had a few more days to run your program!

7

MateiG commented on June 19, 2017, 4:57 p.m.

Lol