Shortest code to generate a list of prime numbers within a given range

Question

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]

Answer 1

Factor + math.primes, 27 bytes

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

Try it online!

Answer 2

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)

Answer 3

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

Answer 4

Perl 5, 48 bytes

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

Try it online!

Answer 5

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

Answer 6

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

Answer 7

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

Answer 8

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.

Answer 9

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.

Answer 10

Charcoal, 15 bytes

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

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
Ｉ               Cast to string
                Implicitly print each prime on its own line

Answer 11

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

Answer 12

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.

Answer 13

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.

Answer 14

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

Answer 15

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.