33
\$\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

41 Answers 41

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\$

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\$

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\$
1
\$\begingroup\$

Zsh, 101 92 91 90 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, -1 by replacing a && with a ,.

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! Try it online!

57 48 bytes to the prime testing function, 43 41 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\$

Wolfram Language (Mathematica), 22 bytes

RiemannR/*Round/*Prime

Try it online!

This is an approximate solution that by chance works for all of the given test cases, but gives a slightly wrong result for other inputs. The Riemann R function is an approximation of the prime-counting function, which we round to the nearest integer and then request the prime number of that index.

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

C (gcc), 78 65 bytes

f(n,i,j){for(i=j=0;j-1;i++)for(j=n+=i%2?-i:i;--j,n-1&&n%j;);i=n;}

Try it online!

f(n,i,j){
    for(i=j=0;j-1;i++)      //while j!=1
        for(j=n+=i%2?-i:i;  // step to next closest value to original input n
            --j,n-1&&n%j;); // find greatest factor which is less than j
    i=n;                    //return
}
\$\endgroup\$
  • \$\begingroup\$ @ceilingcat division by 0 when n=1 \$\endgroup\$ – attinat Aug 26 at 22:32
1
\$\begingroup\$

TI-BASIC (TI-84+), 74 Bytes

Ans→A:{2,3→A:For(P,5,2A,2:If min(remainder(P,seq(X,X,3,1+√(P),2:P→∟A(1+dim(∟A:End:abs(A-∟A:∟A(1+sum(not(cumSum(Ans=min(Ans

Hexdump:
(Token hex-values found here.)

72 04 41 3E 08 32 2B 33 04 41 3E D3 50 2B 35 2B | Ans→A:{2,3→A:For(P,5,
32 41 2B 32 3E CE 1A EF 32 50 2B 23 58 2B 58 2B | 2A,2:If min(remainder(P,seq(X,X,
33 2B 31 70 BC 50 11 2B 32 3E 50 04 EB 41 10 31 | 3,1+√(P),2:P→∟A(1
70 B5 EB 41 3E D4 EE B2 41 71 EB 41 3E EB 41 10 | +dim(∟A:End:abs(A-∟A:∟A(
31 70 B6 B8 BB 29 72 6A 1A 72                   | 1+sum(not(cumSum(Ans=min(Ans

Input is an integer in Ans. Output is printed implicitly.
Note: due to limitations on how large lists can be, \$A\$ is limited to \$0 \le A \le 3953\$

Explanation:

Ans→A                                  ;store the input in a variable called "A"
{2,3→A                                 ;store the list {2 3} into a list called "A"
For(P,5,2A,2                           ;loop from 5 to two times the input using a step
                                       ; of 2
                   seq(X,X,3,1+√(P),2  ;generate a list of integers from 3 to 1 + the
                                       ; square root of the loop counter using a step of 2
                                       ; (e.g. P=21, list={3 5})
       remainder(P,                    ;then take the loop counter modulo each element
                                       ; (e.g. P=21, list={0 1})
If min(                                ;if all of the resulting elements are non-zero,
                                       ; then
P→∟A(1+dim(∟A                          ;add the loop counter's value to the list "A", the
                                       ; list of primes
End
abs(A-∟A                               ;subtract the input from the primes list and take
                                       ; the absolute value of each element (distance to
                                       ; each prime)
   1+sum(not(cumSum(Ans=min(Ans        ;find the first index of the minimum value
∟A(                                    ;then use that index to get the value in the primes
                                       ; list at that index
                                       ;implicit output

Examples:

100:prgmCDGF1F
             101
5:prgmCDGF1F
               5
80:prgmCDGF1F
              79
\$\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.