## 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, 5:08 p.m.

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

• 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

• commented on Sept. 21, 2022, 1:42 a.m. edited

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

• 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 , there must be a prime number within the range of , and this may help you (And I finally passed this problem by using this property)

• 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 to determine whether or not it is prime?

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

Does anyone know how to make my program run faster?

• 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.

• commented on March 12, 2020, 2:14 p.m. edited

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

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

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

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

• 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.

• commented on Nov. 15, 2017, 12:19 a.m. edited

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

• 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.

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

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

• 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.

• 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.

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

You know edits are visible to everyone, right?

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

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

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

Time Limit Exceeded

• 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.

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

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

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

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

• 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?

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

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

• 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.

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

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

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

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

• 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.

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

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

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

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

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

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

• 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.

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

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

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

Inputs are integer only.

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

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

• 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++;

• 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!

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

Lol