## Next Prime (Hard)

View as PDF

Points: 15
Time limit: 1.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C++, COBOL, CommonLisp, Dart, Forth, Fortran, Intercal, Lisp, Octave, Pascal, Prolog, Python, Racket, Rust, Scheme, Sed, TCL, Text, Turing, VB
##### Brute Force Practice 3 — Hard Version

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 May 28, 2020, 10:50 a.m.

Can Java be allowed with BigInteger disabled? Like a+b hard.

• commented on March 29, 2020, 6:02 p.m. edit 3

Fermat primality test WA for case 13.

Edit: try dividing by first 100000 primes passes it

• commented on Dec. 29, 2020, 8:16 p.m.

dividing by less than first 50k primes passes it

• commented on Dec. 30, 2020, 1:10 a.m.

First 40k is enough

• commented on Jan. 6, 2021, 2:27 p.m.

*38k

• commented on March 9, 2019, 6:27 p.m.

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

• commented on Aug. 21, 2019, 1:16 p.m. edit 2

PHP shouldn't be allowed on dmoj at all

• commented on Nov. 5, 2018, 6:17 p.m.

Why is there an AC Java 9 submission

• commented on Oct. 23, 2018, 10:00 p.m.

cases #3-10 give me a WA any tips?

• commented on Oct. 24, 2018, 6:42 a.m.

Look at the constraints on N. Also a tip you can use i*i<n instead of i<sqrt(n) to be sure that the calculations are precise.

• commented on Oct. 24, 2018, 1:13 p.m.

i*i < n gives me a TLE

• commented on Oct. 25, 2018, 1:53 p.m. edited

TLE means that your code is too slow.

• commented on Oct. 8, 2017, 11:14 a.m.

Hint

can I have any hints?

keep getting WA MLE and TLE.

• commented on Oct. 8, 2017, 12:59 p.m.

Your code is wrong, takes up too much memory, and is too slow.

• commented on Nov. 15, 2017, 10:43 p.m.

Thx man.

I'm probably just gonna learn some math.

• commented on Oct. 4, 2017, 10:07 p.m.

Why is java disabled?

• commented on Oct. 4, 2017, 11:13 p.m.

java.math.BigInteger has a method called isProbablePrime(), which would trivialize the problem.

• commented on Nov. 13, 2017, 7:53 p.m.

oh ok

• commented on April 16, 2017, 1:57 a.m.

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

• commented on April 16, 2017, 3:41 a.m.

The time is the total time, not the average

• commented on Nov. 13, 2017, 9:19 p.m.

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

• commented on April 17, 2017, 10:32 p.m.

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

• commented on Oct. 15, 2016, 1:44 p.m.

What is submitting code in python not allowed for this problem?

• commented on June 1, 2017, 11:08 a.m.

Can we have Python <3

• commented on Jan. 21, 2017, 5:35 p.m.

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

• commented on Sept. 18, 2016, 2:08 a.m.

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

• commented on March 23, 2015, 8:10 p.m.

Partial output is disabled for this problem.