Next Prime (Hard)

View as PDF
Submit solution
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 N (1 \le N \le 10^{18})

Output

Print the number you want.

Sample Input

4

Sample Output

5

Comments


  • 3
    noYou  commented on May 28, 2020, 10:50 a.m.

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


  • 2
    harry7557558  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


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

      dividing by less than first 50k primes passes it


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

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


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

      PHP shouldn't be allowed on dmoj at all


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

    Why is there an AC Java 9 submission


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

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


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


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

        i*i < n gives me a TLE


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

          TLE means that your code is too slow.


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

    Hint

    can I have any hints?

    keep getting WA MLE and TLE.


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

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


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

        Thx man.

        I'm probably just gonna learn some math.


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

    Why is java disabled?


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

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


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

        oh ok


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

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


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

      The time is the total time, not the average


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

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


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

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


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

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


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

      Can we have Python <3


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

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


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

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


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

    Partial output is disabled for this problem.