32
\$\begingroup\$

Challenge

This is a simple one: Given a positive integer up to 1,000,000, return the closest prime number.

If the number itself is prime, then you should return that number; if there are two primes equally close to the provided number, return the lower of the two.

Input is in the form of a single integer, and output should be in the form of an integer as well.

I don't care how you take in the input (function, STDIN, etc.) or display the output (function, STDOUT, etc.), as long as it works.

This is code golf, so standard rules apply—the program with the least bytes wins!

Test Cases

Input  =>  Output
------    -------
80     =>      79
100    =>     101
5      =>       5
9      =>       7
532    =>     523
1      =>       2
\$\endgroup\$
  • 5
    \$\begingroup\$ Hi and welcome to PPCG!. To avoid down voting due to lack of quality I suggest you to post it to the sandbox first and after a couple of days post it here \$\endgroup\$ – Luis felipe De jesus Munoz Mar 27 at 15:17
  • \$\begingroup\$ This is one of the outputs requested in this challenge. \$\endgroup\$ – Arnauld Mar 27 at 15:24
  • \$\begingroup\$ Very closely related but not quite identical. \$\endgroup\$ – Giuseppe Mar 27 at 15:35
  • \$\begingroup\$ @Arnauld I saw that one, but I thought that they were different enough to warrant a new question. \$\endgroup\$ – Nathan Dimmer Mar 27 at 15:37
  • 2
    \$\begingroup\$ See also OEIS A051697. \$\endgroup\$ – Eric Towers Mar 28 at 8:52

39 Answers 39

1
\$\begingroup\$

Swift, 186 bytes

func p(a:Int){let b=q(a:a,b:-1),c=q(a:a,b:1);print(a-b<=c-a ? b:c)}
func q(a:Int,b:Int)->Int{var k=max(a,2),c=2;while k>c && c != a/2{if k%c==0{k+=b;c=2}else{c=c==2 ? c+1:c+2}};return k}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Jelly, 14 bytes

ÆpæRÆnạÞƲ2>?2Ḣ

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Zsh, 101 92 91 bytes

-9 by collapsing the body into the head of p's loop, -1 from using i=j instead of i=$1 in main loop.

p(){for ((n=2;n<$1&&$1%n++;)):
(($1==n))&&<<<$1}
j=$1
for ((i=j;;++j&&--i))p $i||p $j&&exit

Try it online!

Try it online!

57 48 bytes to the prime testing function, 43 42 bytes to the main loop (1 byte to the newline between them):

p(){  # prime function: takes one input, outputs via return code
for (( n = 2; n < $1 && $1 % n++; ))   # divisibility check in loop header
    :                 # no-op loop body
(( $1 == n )) &&      # if we looped up to $1:
    <<< $1            #     echo out $1. Otherwise, this will return false
}

For the last condition, we can't use the shorter (($1-n))||, because we need to return false to the main loop if we didn't find a prime. We print in the function to avoid complexity in the main loop.

j=$1                          # set i = j = $1. Doing one in and one out is smallest
for (( i = j; ; ++j && --i )) # loop indefinitely, increment and decrement
    p $i || p $j && exit      # if either $i or $j was a prime, exit

Conditionals are left-associative, which we take advantage of here. We do test the starting number twice to make the decrement logic simpler.

\$\endgroup\$
1
\$\begingroup\$

Python 2, 93 bytes

lambda n:sorted(range(1,3*n),key=lambda x:abs(x-n)if all(x%k for k in range(2,x))else 2*n)[0]
\$\endgroup\$
  • 1
    \$\begingroup\$ You don't need the f= in the start \$\endgroup\$ – Embodiment of Ignorance Mar 27 at 20:46
  • \$\begingroup\$ @EmbodimentofIgnorance Thanks, fixed that along with the range and non-prime penalty criteria that was causing n=1 to fail \$\endgroup\$ – deustice Mar 27 at 21:00
  • 1
    \$\begingroup\$ The primality check doesn't work for Fermat pseudoprimes such as 341=31*11 which it calls prime. \$\endgroup\$ – xnor Mar 27 at 21:16
1
\$\begingroup\$

Ruby, 67 bytes

def p n;n.prime?;end;def a b,c=0;p(b-c)?b-c:p(b+c)?b+c:a(b,c+1);end

Try it online!

\$\endgroup\$
1
\$\begingroup\$

C (gcc), 78 bytes

f(n,i){for(i=0;c(n);n+=++i%2?-i:i);i=n;}c(n,i){for(i=1;n%++i*~-n;);n=n<2|i<n;}

Try it online!

f(n,i){                     //main function
    for(i=0;c(n);           //while n is nonprime
        n+=++i%2?-i:i);     //step to next closest value to the original input n
    i=n;                    //return n
}
c(n,i){                     //check if number is nonprime
    for(i=1;n%++i           //increment i until i|n
                *~-n;);     // or just exit the loop if n==1
    n=n<2                   //return true if either n<2 (n=0 or n=1)
        |i<n;               // or n is composite (∃i,1<i<n:i|n)
}
\$\endgroup\$
1
\$\begingroup\$

TSQL query, 155 bytes

USE master
DECLARE @ INT=1000000;

WITH C as(SELECT abs(number-500+@)r,abs(number)+2s
FROM spt_values)SELECT top 1r FROM c
WHERE 0not in(SELECT c.r%s FROM c d
WHERE c.r>s)ORDER BY abs(r-@),r

Try it online

\$\endgroup\$
  • \$\begingroup\$ @TobySpeight thanks for improving my answer. Can you please explain what this <!-- language-all: lang-sql --> does? Is it something I should include in all my answers ? \$\endgroup\$ – t-clausen.dk Mar 28 at 19:24
  • 1
    \$\begingroup\$ That's a prettify hint; you can find out about it near the end of Editing Help. \$\endgroup\$ – Toby Speight Mar 28 at 22:18
1
\$\begingroup\$

C# (Visual C# Interactive Compiler), 87 bytes

n=>{int i=0;for(;n<2||Enumerable.Range(2,n-2).Any(x=>n%x<1);n+=++i%2<1?-i:i);return n;}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Ruby -rprime, 39 bytes

Relies on the idea that for any positive integer \$n\$, the \$n\$th prime is always larger than \$n\$.

->n{Prime.take(n).min_by{|i|(i-n).abs}}

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.