1

Consider the follwing problem:

Given $n$ (in binary) output a prime number $p \geq n$ (not necessarily the first prime number after $n$)

Are there better techniques than the trivial one that scans $n,n+1,n+2,...$ until a prime is found?

And can we do better if the full factorization of $n$ is given?

Vor
  • 690
  • 1
    If $n$ is even, there's no point looking at $n+2,n+4,\dots$; if $n$ is odd, no point scanning $n+1,n+3,\dots$. There are tricks like that, that save some work. I don't think there's much else. – Gerry Myerson Mar 26 '14 at 10:27

2 Answers2

2

A major optimization of your method would be

if n<2**74207281-1:
    return 2**74207281-1
else:
    n=n|1 #makes n odd
    while True:
        if is_prime(n):
            return n
        n+=2
Oscar Smith
  • 547
  • 1
    How about "if $n$ has fewer than $74207281$ binary digits, return $2^{74207281}-1$, else..."? – Barry Cipra Aug 22 '16 at 18:17
  • Wow, that is way more optimized. I'll edit now. – Oscar Smith Aug 22 '16 at 18:19
  • I thought about using a method where you would look up the largest prime at mersene.com every second until there was one greater than the input number, which would be massively faster, but then the code becomes less trivial. – Oscar Smith Aug 22 '16 at 18:22
  • Actually that's a very nice idea! You might have the code spend part of its time searching for the next prime and most of its time checking mersenne.com. That would guarantee the code will produce an answer in finite time. – Barry Cipra Aug 22 '16 at 18:30
  • Basically "if n < largest known prime return largest known prime else join the salt mines and start looking for larger prime" I guess that follows the letter of the problem, but it really doesn't follow the spirit of the problem, do you think? I mean it doesn't address how to find primes.... which admittedly there is no good answer. I'll grant this answer is cute. Oh, heck. +1 for being overly literal and letting that be a warning to others. – fleablood Aug 22 '16 at 18:48
1

Currently, there is no method known to construct arbitary large prime numbers, so the problem is currently out of reach.

A solution to this problem would be very useful because high rewards have been promised to find large prime numbers.

Peter
  • 84,454