5
\$\begingroup\$

Strangely never asked before, this question pertains to the generation of a list of prime numbers within a given range using the shortest possible code. Several algorithms, such as the Sieve of Eratosthenes and trial division, are known to be effective for this purpose, but require significant code length. Is there an alternative approach or trick that can be used to generate a list of prime numbers in a more concise manner?

The focus of this question is on the optimization of code length, so answers should try to make their code as short as possible. Answers in any programming language are welcome. May the shortest code win!

Format

You must accept two positive integers and output a list of integers in any reasonable format.

Rules

  • Your code doesn't need to handle numbers less than one.
  • The range should be exclusive, i.e., (a..b) instead of [a..b] or [a..b).
  • Either ascending or descending ranges should be supported.
  • Standard loopholes are forbidden.

Test cases

11 59 -> [13,17,19,23,29,31,37,41,43,47,53]
11 3  -> [7,5]
2 2   -> []
2 3   -> []
2 4   -> [3]
4 2   -> [3]
\$\endgroup\$
16
  • 1
    \$\begingroup\$ Welcome to Code Golf, and nice first challenge! In the future, it's reccomended to use the Sandbox to work out the specification of challenges better. Should the program take two integers and find the prime numbers included in the range between them, or can it take a list of the entire range? \$\endgroup\$
    – noodle man
    Feb 24, 2023 at 20:50
  • 1
    \$\begingroup\$ Thanks, by list I mean what you said: "the program take two integers and find the prime numbers included in the range between them" \$\endgroup\$ Feb 24, 2023 at 20:51
  • 1
    \$\begingroup\$ Does the output have to be in order of lowest to highest? \$\endgroup\$
    – noodle man
    Feb 24, 2023 at 20:56
  • 2
    \$\begingroup\$ "Optimization of code length, without sacrificing efficiency or accuracy" What do you mean exactly? If you don't sacrifice everything else you are not truly optimizing \$\endgroup\$
    – Luis Mendo
    Feb 24, 2023 at 21:39
  • 3
    \$\begingroup\$ Not sacrificing efficiency is an unusual requirement in a code golf challenge. Also with no info on how to measure score. For instance, if answer A is 100 bytes and answer B is 101 bytes but twice as fast, is A or B the better answer then? \$\endgroup\$
    – Kjetil S
    Feb 25, 2023 at 0:30

15 Answers 15

4
\$\begingroup\$

Factor + math.primes, 27 bytes

[ (a,b) [ prime? ] filter ]

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ Could the exclusive range version still use the builtin, just first increment a and decrement b, or would that be longer than filtering? \$\endgroup\$
    – noodle man
    Feb 24, 2023 at 21:20
  • 1
    \$\begingroup\$ @Jacob Longer by 3 bytes. \$\endgroup\$
    – chunes
    Feb 24, 2023 at 21:22
4
\$\begingroup\$

Vyxal, 4 bytes

+1 byte from @Jacob for informing me about the requirement for exclusive range

rḢ'æ

Try it Online!

Finds all the primes between the first input and the second input (exclusive).

Explanation

r      # Get the range from [<input 1>, ..., <input 2>-1]
 Ḣ     # Remove the first value (so it's exclusive on both ends)
  '    # of that range, filter....
   æ   # only those which are prime
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Ninja'd by 30 seconds :( yours is shorter anway, I was going to find the intersection of the range and the infinite primes list \$\endgroup\$
    – noodle man
    Feb 24, 2023 at 20:58
  • 1
    \$\begingroup\$ OP clarified that range must be exclusive \$\endgroup\$
    – noodle man
    Feb 24, 2023 at 21:05
3
\$\begingroup\$

05AB1E, 5 bytes

Ÿ¦¨ʒp

Try it online or verify all test cases.

Explanation:

Ÿ      # Convert the (implicit) input-pair to an inclusive list
 ¦¨    # Remove both the first and last item to make it an exclusive list
   ʒ   # Filter it by:
    p  #  Check whether the number is a prime
       # (after which the filtered list is output implicitly)
\$\endgroup\$
3
\$\begingroup\$

Perl 5, 48 bytes

sub{grep{(1x$_)!~/^1$|^(11+)\1+$/}1+pop.."@_"-1}

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Japt, 6 bytes

oV Åfj

Try it

Essentially equivalent to 97.100.97.109's answer, though developed independently. Gets the exclusive range by getting the inclusive range between \$[n_1+1,n_2-1]\$. -2 bytes thanks to Shaggy

Explanation:

oV Åfj  full program
oV      the inclusive range between the two inputs
   Å    cut off the first and last elements
    f   filter, keeping only those that
     j    are prime

Japt, 5 bytes

Inclusive range, which was banned after writing this

oV fj
oV  the range from input 1 to input 2
f   filter, keeping only those that
 j    are prime
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 6 bytes \$\endgroup\$
    – Shaggy
    Feb 24, 2023 at 23:57
  • \$\begingroup\$ @Shaggy We like to do a bit of forgetting the builtins \$\endgroup\$
    – noodle man
    Feb 25, 2023 at 0:04
2
\$\begingroup\$

Arturo, 35 bytes

$=>[select chop drop@&..&1=>prime?]

Try it

$=>[          ; anonymous function
    select    ; take elements from
    chop      ; remove last element
    drop .. 1 ; remove first element
    @&..&     ; inclusive input range, reified
    =>prime?  ; that are prime
]             ; end function
\$\endgroup\$
2
\$\begingroup\$

Java 10, 137 bytes

(a,b)->{var r=new java.util.Stack();int t=0,i;for(a^=b<a?b^(t=b=a):0;++a<b;){for(i=a;a%--i>0;);if(i<2)r.add(t<1?r.size():0,a);}return r;}

Try it online.

Explanation:

(a,b)->{                      // Method with two integer parameters and List return-type
  var r=new java.util.Stack();//  Result-list, starting empty
  int t=0,i;                  //  Temp-integers
  for(a^=b<a?                 //  If `b` is smaller than `a`:
          b^(t=b=a):0;        //   Set `t` to `a`,
                              //   and then swap `a` and `b` by using bitwise XORs
      ++a<b;){                //  Loop in the range (a,b):
    for(i=a;                  //   Set `i` to the current `a`
        a%--i>0;);            //   Decrease `i` before every iteration with `--i`,
                              //   and continue as long as `a` is NOT divisible by `i`
    if(i<2)                   //   If `i` is 1 after the loop (which means `a` is a prime):
      r.add(t<1?              //    If `t` is 0 (which means `a` was already smaller than
                              //    or equal to `b`):
                r.size()      //     Append to the result-list
               :              //    Else (`a` was larger than `b`):
                0,            //     Prepend to the result-list instead
            a);}              //    The current prime `a`
  return r;}                  //  And finally return the result-list

Unlike my 05AB1E answer, the exclusive range is actually an advantage for my Java answer, since checking whether a number \$n\geq2\$ is a prime is 3 bytes shorter than checking whether a number \$n\geq1\$ is a prime (see section Primes in this Java tip of mine).


Since I was curious: using an IntStream is apparently 144 143 bytes:

a->b->java.util.stream.IntStream.iterate(a<b?a+1:a-1,i->b<a?i-1:i+1).limit(a<b?b+~a:a>b?a+~b:0).filter(k->{int i=k;for(;k%--i>0;);return i<2;})

-1 byte thanks to @Neil.

Try it online.

Explanation:

a->b->                        // Method with two integer parameters and IntStream return
 java.util.stream.IntStream   //  Create an IntStream
  .iterate(a<b?               //  If `a` is smaller than `b`
            a+1               //   Start at `a+1`
           :                  //  Else (a>=b):
            a-1,              //   Start at `a-1` instead
           i->                //  In every iteration:
              b<a?            //   If `b` is smaller than `a`:
                  i-1         //    Decrement once
                 :            //   Else (b>=a)
                  i+1)        //    Increment once instead
  .limit(a<b?                 //  If `a` is smaller than `b`:
             b+~a             //   Do `b-a-1` amount of iterations
         :a>b?                //  Else-if `a` is larger than `b`:
              a+~b            //   Do `a-b-1` amount of iterations
         :                    //  Else (`a` equals `b`):
          0)                  //   Make the IntStream empty
  .filter(k->{                //  Then filter this IntStream by:
    int i=k;for(;k%--i>0;);return i<2;})
                              //   Primes-check similar as above
\$\endgroup\$
3
  • 1
    \$\begingroup\$ a<b?b+~a:a>b?a+~b:0 should save a byte. \$\endgroup\$
    – Neil
    Feb 25, 2023 at 9:42
  • \$\begingroup\$ Actually, what's wrong with a<b?a+1:b+1,i->i+1? \$\endgroup\$
    – Neil
    Feb 25, 2023 at 9:43
  • \$\begingroup\$ @Neil Ah, of course.. Thanks for the -1. As for the question in your second comment: a descending input would result in an ascending result-list in that case (e.g. the 11,3 results in [5,7] instead of [7,5]). \$\endgroup\$ Feb 25, 2023 at 16:00
2
\$\begingroup\$

Retina 0.8.2, 62 52 bytes

.+
$*
O`
M!&`(?<=(1+)¶1+)1+\1
A`^(11+)\1+$
O`
1+
$.&

Try it online! Takes inputs on separate lines but link is to test suite that splits on comma for convenience. Explanation:

.+
$*

Convert to unary.

O`

Sort into order.

M!&`(?<=(1+)¶1+)1+\1

Generate the exclusive range.

A`^(11+)\1+$

Remove any composite numbers.

O`

Sort into order.

1+
$.&

Convert any remaining numbers to decimal.

\$\endgroup\$
1
  • \$\begingroup\$ I always forget that you can find prime numbers with Regex \$\endgroup\$
    – noodle man
    Feb 24, 2023 at 22:39
1
\$\begingroup\$

Excel, 122 bytes

=LET(
    a,A1,
    b,B1,
    c,a>b,
    d,SEQUENCE(IF(c,a,b)-1),
    SORT(FILTER(d,(d>IF(c,b,a))*MMULT(N(MOD(d,TRANSPOSE(d))=0),d^0)=2,""),,-1^c)
)

Inputs in cells A1 and B1.

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

Charcoal, 15 bytes

IΦ…⊕⌊θ⌈θ⬤…²ι﹪ιλ

Try it online! Link is to verbose version of code. Takes input as a list. Explanation:

  …             Range from
     θ          Input list
    ⌊           Minimum
   ⊕            Incremented
       θ        To input list
      ⌈         Maximum
 Φ              Filtered where
         …      Range from
          ²     Literal integer `2`
           ι    To current value
        ⬤       All members satisfy
             ι  Outer value
            ﹪   Modulo i.e. is not divisible by
              λ Inner value
I               Cast to string
                Implicitly print each prime on its own line
\$\endgroup\$
1
\$\begingroup\$

Jelly, 4 bytes

æRḟ,

A dyadic Link that accepts the one bound on the left and the other bound on the right and yields a list of primes strictly between the bounds.

Try it online!

How?

æRḟ, - Link: integer, A; integer, B
æR   - inclusive prime range -> list of primes between A and B, inclusive
   , - pair -> [A, B]
  ḟ  - filter discard -> list of primes between A and B, exclusive
\$\endgroup\$
1
\$\begingroup\$

Regex (ECMAScript 2018), 54 53 48 bytes

x(?=(x+))(?<=(?=.*\b(?!\1)x+\b).*)(?!(xx+)\2+\b)

Try it online!

Takes its input in unary, as two strings of x characters whose lengths represent the two numbers, joined/separated by a ,. Returns its output in unary as the list of matches' \1 captures, whose lengths represent the prime numbers in the range.

-1 byte thanks to Neil, by leaving out an unneeded ≥2 assertion
-5 bytes by handling ascending and descending ranges all in one go rather than separately

x                 # tail -= 1; force the top end of the range to be excluded;
                  # X = tail
(?=(x+))          # Capture \1 = tail
(?<=              # Variable-length lookbehind, evaluated right-to-left:
    (?=           # Lookahead (evaluated left-to-right):
        .*\b      # Skip tail over to a word boundary, which could be the
                  # beginning or end of the string, or either side of a comma.
        (?!\1)    # Assert tail < \1, i.e. along with the word boundary
                  # assertion above, that this is the bottom end of the range,
                  # implying \1 was captured from the upper end of the range.
        x+\b      # Assert tail >= 1
    )
    .*            # Skip all the way to the beginning, then evaluate the above
)
(?!(xx+)\2+\b)    # Assert tail is not composite; tail > 1 was already asserted
                  # above, so along with that, this asserts tail is prime.
\$\endgroup\$
2
  • 1
    \$\begingroup\$ tail > \1 forces tail >= 2 since \1 >= 1. \$\endgroup\$
    – Neil
    Feb 25, 2023 at 9:46
  • \$\begingroup\$ @Neil Thanks. As you probably guessed, I started by writing a regex that handles inclusive ranges (in which the explicit tail>=2 assertion was needed), and only afterward modified it to do exclusive ranges. \$\endgroup\$
    – Deadcode
    Feb 25, 2023 at 17:20
1
\$\begingroup\$

Python, 67 bytes

lambda a,b:[n for n in range(a+1,b)if all(n%m for m in range(2,n))]

Attempt This Online!

The challenge has now been edited to allow either ascending or descending ranges, so this only supports ascending.

\$\endgroup\$
0
\$\begingroup\$

Thunno, \$5\log_{256}(96)\approx\$ 4.12 bytes

:ZTgN

Attempt This Online! Takes the inputs in reverse order.

Explanation

:ZTgN # Inputs: x and y
:     # Push [x..y)
 ZT   # Remove first item
   gN # Filter for primes
\$\endgroup\$
0
\$\begingroup\$

Mathematica (Wolfram Language), 61 Bytes

I'm new at this, but I thought this is a good problem to practice on.

Select[Range[First[Sort[{##}]]+1,Last[Sort[{##}]]-1],PrimeQ]&

Try it out online

This is a functional implementation, which takes a list of two numbers, orders them, and generates all integers in the open interval (input 1, input 2). Then the select function picks out all the prime elements of that interval.

I'll keep thinking about how to shorten this code.

EDIT: Added all the test cases on tio.run, and implemented Range function.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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