Next Prime

View as PDF

Points: 5
Time limit: 2.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
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

The first line will have the integer ()

Output

Print the number you want.

Sample Input

4

Sample Output

5

• 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 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. 3, 2020, 10:10 p.m. edited

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on Feb. 2, 2020, 7:56 p.m.

This comment is hidden due to too much negative feedback. Click here to view it.

• 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 Jan. 17, 2019, 11:07 a.m. edited

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on Jan. 17, 2019, 12:53 p.m.

think about factors of prime numbers

• commented on Oct. 13, 2018, 9:31 a.m.

This comment is hidden due to too much negative feedback. Click here to view it.

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

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on June 27, 2018, 9:24 p.m.
• commented on Nov. 14, 2017, 7:19 p.m. edited

This comment is hidden due to too much negative feedback. Click here to view it.

• 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. Click here to view it.

• 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. 15, 2015, 8:31 p.m.

This comment is hidden due to too much negative feedback. Click here to view it.

• 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. Click here to view it.

• 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. Click here to view it.

• 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. Click here to view it.

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

This comment is hidden due to too much negative feedback. Click here to view it.

• 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. Click here to view it.

• 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. Click here to view it.

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

Does it have to work for decimals?

• 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