## Next Prime

View as PDF

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 .

#### Output Specification

Print the number you want.

#### Sample Input

4

#### Sample Output

5

• commented on Sept. 25, 2022, 1:08 p.m.

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

• commented on July 17, 2020, 9:43 a.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

• commented on Sept. 20, 2022, 9:42 p.m.

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

• commented on Sept. 20, 2022, 9:41 p.m.

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

• commented on July 17, 2020, 11:08 a.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 to determine whether or not it is prime?

• commented on Feb. 22, 2019, 10:24 p.m.

Does anyone know how to make my program run faster?

• commented on March 11, 2020, 10:56 p.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.

• commented on March 12, 2020, 10:14 a.m.

Yes, because that uses the miller-rabin primality test, which is time on adverage, where is the number of times the test is performed, which is generally a small constant number.

• commented on Feb. 22, 2019, 10:34 p.m.

• commented on June 27, 2018, 8:44 p.m.

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

• commented on Dec. 2, 2021, 10:40 p.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.

• commented on Nov. 14, 2017, 7:19 p.m. edited

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

• commented on Nov. 15, 2017, 11:21 p.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.

• commented on Feb. 26, 2020, 12:49 a.m.

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

• commented on July 18, 2021, 11:04 a.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.

• commented on Nov. 28, 2017, 4: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.

• commented on Oct. 5, 2022, 1:22 p.m.

You know edits are visible to everyone, right?

• commented on Oct. 15, 2015, 8:31 p.m.

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

• commented on Jan. 26, 2019, 6:44 p.m.

Time Limit Exceeded

• commented on Oct. 15, 2015, 8:37 p.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.

• commented on Jan. 6, 2015, 5:08 p.m.

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

• commented on Jan. 6, 2015, 5:55 p.m.

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

• commented on Nov. 14, 2014, 2: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?

• commented on Nov. 14, 2014, 3:34 a.m.

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

• commented on Nov. 14, 2014, 11:27 a.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.

• commented on Nov. 24, 2014, 10:06 p.m.

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

• commented on Nov. 24, 2014, 10:08 p.m.

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

• commented on Nov. 24, 2014, 10:51 p.m.

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

• commented on Oct. 27, 2014, 8:47 p.m.

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

• commented on Oct. 27, 2014, 9:13 p.m.

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

• commented on Oct. 27, 2014, 9:59 p.m.

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

• commented on Oct. 27, 2014, 10:01 p.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.

• commented on Oct. 16, 2014, 9:28 p.m.

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

• commented on Oct. 16, 2014, 11:32 p.m.

Inputs are integer only.

• commented on Sept. 27, 2014, 9:59 p.m.

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

• commented on May 5, 2018, 4:51 a.m.

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

• commented on Sept. 27, 2014, 11:43 p.m.

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

• commented on June 19, 2017, 12:57 p.m.

Lol