37
\$\begingroup\$

Write the shortest code for finding the sum of primes between \$a\$ and \$b\$ (inclusive).

Input

  1. \$a\$ and \$b\$ can be taken from command line or stdin (space seperated)
  2. Assume \$1 \le a \le b \le 10^8\$

Output Just print the sum with a newline character.

Bonus Points

  1. If the program accepts multiple ranges (print one sum on each line), you get extra points. :)
\$\endgroup\$
9
  • \$\begingroup\$ The upper limit is too big to allow many interesting solutions (if they have to complete in reasonable time, at least). \$\endgroup\$
    – hallvabo
    Commented Jan 28, 2011 at 9:13
  • 2
    \$\begingroup\$ @hallvabo You find inefficient solutions interesting? \$\endgroup\$ Commented Jan 28, 2011 at 9:25
  • \$\begingroup\$ @hallvabo, That's ok. I don't think anyone minds an ineffcient solution. If other's object, i'll be more than happy to lower the limit \$\endgroup\$
    – st0le
    Commented Jan 28, 2011 at 9:38
  • \$\begingroup\$ Just made and ran a not very optimised or concise version of the program in C#, using 1 to 10^8. Assuming my algorithm's correct, it ran in under 1m30s, and didn't overflow from a long. Seems like a fine upper limit to me! \$\endgroup\$
    – Nellius
    Commented Jan 28, 2011 at 12:08
  • \$\begingroup\$ A quick easy check: sum of primes between 1 and 100 = 1060. \$\endgroup\$
    – Nellius
    Commented Jan 28, 2011 at 12:50

61 Answers 61

1
\$\begingroup\$

Perl, 103 chars

while(<>){($a,$b)=split/ /;for($a..$b){next if$_==1;for$n(2..$_-1){$_=0if$_%$n==0}$t+=$_;}print"$t\n";}

It'll accept multiple space separated lines and give the answer for each :D

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

Mathematica, 27

Predefined a and b:

a~Range~b~Select~PrimeQ//Tr

As a function (also 27):

Tr[Range@##~Select~PrimeQ]&
\$\endgroup\$
1
\$\begingroup\$

Python 3: 86 chars

a,b=map(int,input().split())
P=k=1
s=0
while k<=b:s+=P%k*k*(k>=a);P*=k*k;k+=1
print(s)

Uses the factorial trick with Wilson's Theorem to check whether k is prime. P%k is 1 if k is prime and 0 otherwise. If it is prime, k is added to the running sum s.

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

Python - 194

File fsoe-sum.py:

S,E=input()
L={}
n=2
s=0
while n<=E:
        try:
                P=L[n];del L[n]
        except:
                P=[n]
                if S<=n: s+=n
        for p in P:
                m=n+p
                try:
                        if p not in L[m]:L[m].append(p)
                except:
                        L[m] = [p]
        n+=1
print s

Filesize is 194 bytes when using tabs to indent and no final newline.

Not the shortest pythonish solution but do you see the enbedded sieve? ;-)

Run:

$ python fsoe-sum.py
1,1000000
37550402023
$ python fsoe-sum.py
1,2000000
142913828922
$ python fsoe-sum.py
1000001,2000000            
105363426899
$ python -c 'print 142913828922-37550402023'
105363426899
\$\endgroup\$
1
\$\begingroup\$

Perl, 94

my$s;map{my($a,$b)=($_,0);for(2..$a-1){$a%$_==0&&$b++}$b or$s+=$a}($ARGV[0]..$ARGV[1]);print$s

This takes input from the command line. It doesn't use regex.

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

GolfScript, 27 24 bytes

~,>{:x,{)x\%!},,2=},{+}*

This is based off of @w0lf's prime number algorithm.

\$\endgroup\$
1
  • \$\begingroup\$ Could you please add a "how it works"? \$\endgroup\$
    – Someone
    Commented Jan 3, 2021 at 21:08
1
\$\begingroup\$

Ruby, 60 bytes

require'prime';p=->a,b{eval Prime.each(b).reject{|x|x<a}*?+}

Usage

puts p[*gets.split.map(&:to_i)]

Inputs & Outputs

2 10     #=> 10
3 10     #=> 8
100 1000 #=> 75067
\$\endgroup\$
1
\$\begingroup\$

Casio-Basic, 42 bytes

sum(seq(piecewise(isPrime(x),x,0),x,a,b

Uses a hybrid/piecewise function that returns the number if it's prime, otherwise return 0. seq runs this over the range a to b, then sum adds it all up.

39 bytes for the function, 3 bytes to enter a,b as parameters.

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

Haskell, 47 44 bytes

a!b=sum[x|x<-[a..b],all((<)0.mod x)[2..x-1]]

SEJPM helped me save 3 bytes!

\$\endgroup\$
3
  • \$\begingroup\$ 44 bytes: a!b=sum[x|x<-[a..b],all((<)0.mod x)[2..x-1]] (using all instead of and) \$\endgroup\$
    – SEJPM
    Commented Oct 11, 2017 at 12:00
  • \$\begingroup\$ Fails for 1!3 (gives 6 instead of 5).. \$\endgroup\$ Commented Aug 9, 2018 at 0:16
  • \$\begingroup\$ a?b=sum[n|n<-[a..b],n>1,all((>0).mod n)[2..n-1]], works for 1?3 \$\endgroup\$
    – Benji
    Commented Oct 19, 2020 at 15:48
1
\$\begingroup\$

Add++, 10 bytes

L,d@ßrÞP¦+

Try it online!

How it works

D,f,@@,		; Define a dyadic function, f
		; Example arguments:	[2 23]
	d	; Duplicate;	STACK = [2 23 23]
	@	; Reverse;	STACK = [23 23 2]
	ßr	; Range;	STACK = [23 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22]
	Þ	; Filter on:
	  P	;  Primality	STACK = [23 2 3 5 7 11 13 17 19]
	¦+	; Sum;		STACK = [100]
		; Implicitly return top of stack
\$\endgroup\$
1
\$\begingroup\$

APL(NARS), 11 chars, 22 bytes

{+/⍵/⍨0π¨⍵}

test one range:

{+/⍵/⍨0π¨⍵}  1..23
  100
{+/⍵/⍨0π¨⍵}  1..22
  77
{+/⍵/⍨0π¨⍵}1..1
  0

test two ranges:

{+/⍵/⍨0π¨⍵}¨(1..22)(1..23)
  77 100 
\$\endgroup\$
1
\$\begingroup\$

Python 3: 99 chars


l,h=map(int,input().split())
print(sum(p for p in range(l,h+1) if all(p%i for i in range(2,p)))-1)

\$\endgroup\$
4
  • \$\begingroup\$ This is not inclusive. \$\endgroup\$
    – jamylak
    Commented Jul 30, 2012 at 6:23
  • \$\begingroup\$ As noted by jamylak, this is not an inclusive range (try inputs 2 23), and is therefore invalid per the challenge spec. As so, I’ve flagged your answer for deletion. \$\endgroup\$ Commented Oct 16, 2020 at 1:52
  • \$\begingroup\$ I am removing this answer as per our policy on handling invalid submissions. Please feel free to edit this solution so it's valid and flag it for undeletion. \$\endgroup\$
    – hyper-neutrino
    Commented Oct 16, 2020 at 3:19
  • \$\begingroup\$ Whoever reflagged this for deletion, it was undeleted after being edited. I'm marking as "Looks OK", let me know if it's still invalid. \$\endgroup\$
    – rydwolf
    Commented Oct 17, 2020 at 23:19
1
\$\begingroup\$

Python 3: 259 characters This is a longer solution, but it's more efficient than the one-liner I first posted.

import itertools as i
l,h=map(int,input().split())
F=lambda p:lambda x:x%p
def S(s):
 while 1:
  yield (p:=next(s),s:=filter(F(p),s) if p*p<=h else s)[0]
P=lambda:(yield from S(i.count(2)))
print(sum(i.takewhile(lambda e:e<=h,i.dropwhile(lambda e:e<l,P()))))
\$\endgroup\$
1
\$\begingroup\$

Whispers v3, 69 bytes

> Input
> Input
>> 1…2
>> L’
>> Select∧ 4 3
>> ∑5
>> Output 6

Try it online!

simply makes an inclusive range and filters it, then sums it.

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

Python 2, 82 bytes

for i in range(input(),input()+1):P=n=1;exec'P*=n*n;n+=1;'*~-i;exec P%n*'print;'*i

Try it online! Outputs in unary using a newline as a tally mark.

for i in range(input(),input()+1):P=n=1;exec'...'*~-i;exec P%n*'...'*i  # trimmed program
for   in                         :     ;             ;                  # for... 
    i                                                                   # variable...
for   in                         :     ;             ;                  # in...
         range(       ,         )                                       # [...
               input()                                                  # input...
         range(                 )                                       # , ...,
                       input()                                          # input...
                              +                                         # plus...
                               1                                        # literal...
         range(                 )                                       # ]...
                                     =                                  # set...
                                    n                                   # variable...
                                     =                                  # to...
                                      1                                 # literal
                                   =                                    # set...
                                  P                                     # variable...
                                   =                                    # to...
                                    n                                   # variable
                                        exec                            # execute...
                                            '...'                       # literal...
                                                 *                      # repeated...
                                                  ~                     # negative...
                                                   -                    # negative...
                                                    i                   # variable...
                                                  ~                     # minus 1...
                                                 *                      # times...
                                        exec                            # as Python code
                                                      exec              # execute...
                                                               '...'    # literal...
                                                              *         # repeated...
                                                           P            # variable...
                                                            %           # modulo...
                                                             n          # variable...
                                                              *         # times...
                                                                    *   # repeated...
                                                                     i  # variable...
                                                                    *   # times...
                                                      exec              # as Python code

====================

P*=n*n;n+=1;  # full program
 *=           # set...
P             # variable...
 *=           # to...
P             # variable...
 *=           # multiplied by...
   n          # variable...
    *         # multiplied by...
     n        # variable
        +=    # set...
       n      # variable...
        +=    # to...
          1   # literal...
        +=    # added to...
       n      # variable

====================

print;  # full program
print   # output nothing with a trailing newline
\$\endgroup\$
1
\$\begingroup\$

Factor + math.primes, 37 bytes

: f ( x y -- n ) primes-between sum ;

Try it online!

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

Brachylog, 5 bytes

⟦₂ṗˢ+

Try it online!

Explanation

⟦₂       Range from the 2 numbers in the Input
  ṗˢ     Select all primes
    +    Sum
\$\endgroup\$
1
\$\begingroup\$

Thunno, \$ 7 \log_{256}(96) \approx \$ 5.76 bytes

1+:gNkS

Attempt This Online!

Takes \$ b \$ first, then \$ a \$

Explanation

1+:gNkS  # Implicit input, b then a
1+       # Pop b and push b+1
  :      # Pop both and push [a..b+1)
   gNk   # Filter for primes only
      S  # Sum the resulting list
\$\endgroup\$
1
\$\begingroup\$

Stax, 8 bytes

Φ└♪Y╓U↨M

Run and debug it

This is a packed stax program which unpacks to the following 10 bytes:

^|r{|p}f|+

Run and debug it

^|r{|p}f|+ # takes input a,b
^          # increment b
 |r        # range from a..b+1
   {  }f   # filter by
    |p     # is prime?
        |+ # sum
\$\endgroup\$
1
\$\begingroup\$

CJam, 11 bytes

),\>{mp},:+

Try it online!

Essentially a port of my Stax answer

Explanation

),\>{mp},:+ # function taking a,b
)           # increment b
 ,          # range 0..b+1
  \         # swap to put a on top of stack
   >        # drop a elements from the range 0..b+1, essentially making it range(a,b+1)
    {  },   # filter by
     mp     # primality
         :+ # sum
\$\endgroup\$
1
\$\begingroup\$

Arturo, 38 36 bytes

print∑select..loop arg=>do=>prime?

enter image description here

print         ; print
∑             ; sum
select        ; select certain items from a block
..            ; range
loop arg=>do  ; eval each command line argument and place on stack
=>prime?      ; are they prime? (select)
\$\endgroup\$
1
\$\begingroup\$

Vyxal s, 20 bits1, 2.5 bytes

ṡ~æ

Try it Online!

Somehow, I never noticed the existing answer is actually invalid.

Explained

ṡ~æ
ṡ    # Range [a, b]
 ~æ  # Filtered to only contain primes
# Summed by the s flag
\$\endgroup\$
1
\$\begingroup\$

SAS, 130 134

I got suggestion that use of macro variables for input is "invalid method", here is other version of the code which basically wraps the original one (look below) inside a %window statement (makes it more obfuscated and limits it use to the DMS env. only):

The prompt window for DMS:

%window i a 4 b 4;%display i;

[Edit: some spaces were not necessary.] The code that sums primes and prints result to the log

data;array a[&b](. 2:&b);do i=2to sqrt(&b);if a[i]then do j=2*a[i]by a[i]while(j<=&b);a[j]=.;end;end;x=sum(of a&a--a&b);put x;run;

Length of the code which "does the job" effectively stays the same.

Let me share a comment about "invalidity" of the first approach:

Passing input data in all 3 programming interfaces SAS DMS, SAS EG, or SAS Studio can be done:

  1. by a SAS dataset,
  2. by a text file,
  3. hard-coded inside data step, and
  4. by macrovariables.

A programmer does not have to wrap-up 4GL code inside a macro to use macrovariables in it, for example the following works perfectly well:

%let a=42;

data _null_;
  the_answer=&a.;
  put the_answer;
run;

The DMS allows window and display statements and they macro language counterparts %window and %display to produce a prompt input window. Unfortunately those are DMS "specific" and not working in the EG or SAS Studio interfaces.

Assuming we are working in the DMS env. For a SAS programmer execution of the following code, which creates and opens prompt input window:

%window in
@1 'a:' a 8 'b:' b 8;
%display in;

just before the data step and typing in values of a and b

is effectively equivalent to running:

%let a=XXX;
%let b=YYY;

with XXX and YYY as values for a and b.


The original post below:

input in SAS can be done by macrovariables:

%let a=3;
%let b=1000000;

the code sums primes and prints result to the log

data;array a[&b](. 2:&b);do i=2 to sqrt(&b);if a[i] then do j=2*a[i] by a[i] while(j<=&b);a[j]=.;end;end;x=sum(of a&a--a&b);put x;run;

more readable version, _null_ added to stop dataset creation:

%let a=3;
%let b=1000000;
data ;
  array a[&b] (. 2:&b); /* array of integers from 2 to b */
  do i = 2 to sqrt(&b); /* loop until sqrt of b */
    if a[i] then        /* if there is value in the array at i */
      do j=2*a[i] by a[i] while (j<=&b);
        a[j] = .;       /* ... replace all multiplicities of a[i] with missings */
      end;
  end;
  x = sum(of a&a--a&b); /* sum elements for position a to b */
  put x;
run; 
\$\endgroup\$
1
\$\begingroup\$

SAS, 163 bytes

I got suggestion that use of macro variables for input is "invalid method", here is other version of the code which basically wraps the original one (look below) inside a %window statement (makes it more obfuscated and limits it use to the DMS env. only):

The prompt window for DMS:

%window i a 4 b 4;%display i;

The code that sums primes and prints result to the log

data;array a[&b](. 2:&b);do i=2 to sqrt(&b);if a[i] then do j=2*a[i] by a[i] while(j<=&b);a[j]=.;end;end;x=sum(of a&a--a&b);put x;run;

Length of the code which "does the job" effectively stays the same.

Let me share a comment about "invalidity" of the first approach:

Passing input data in all 3 programming interfaces SAS DMS, SAS EG, or SAS Studio can be done:

  1. by a SAS dataset,
  2. by a text file,
  3. hard-coded inside data step, and
  4. by macrovariables.

A programmer does not have to wrap-up 4GL code inside a macro to use macrovariables in it, for example the following works perfectly well:

%let a=42;

data _null_;
  the_answer=&a.;
  put the_answer;
run;

The DMS allows window and display statements and they macro language counterparts %window and %display to produce a prompt input window. Unfortunately those are DMS "specific" and not working in the EG or SAS Studio interfaces.

Assuming we are working in the DMS env. For a SAS programmer execution of the following code, which creates and opens prompt input window:

%window in
@1 'a:' a 8 'b:' b 8;
%display in;

just before the data step and typing in values of a and b

is effectively equivalent to running:

%let a=XXX;
%let b=YYY;

with XXX and YYY as values for a and b.


  • The original post below:*

input in SAS can be done by macrovariables:

%let a=3;
%let b=1000000;

the code sums primes and prints result to the log

data;array a[&b](. 2:&b);do i=2 to sqrt(&b);if a[i] then do j=2*a[i] by a[i] while(j<=&b);a[j]=.;end;end;x=sum(of a&a--a&b);put x;run;

more readable version, _null_ added to stop dataset creation:

%let a=3;
%let b=1000000;
data ;
  array a[&b] (. 2:&b); /* array of integers from 2 to b */
  do i = 2 to sqrt(&b); /* loop until sqrt of b */
    if a[i] then        /* if there is value in the array at i */
      do j=2*a[i] by a[i] while (j<=&b);
        a[j] = .;       /* ... replace all multiplicities of a[i] with missings */
      end;
  end;
  x = sum(of a&a--a&b); /* sum elements for position a to b */
  put x;
run; 
\$\endgroup\$
0
0
\$\begingroup\$

Python, 133

A little bit of sorcery:

x,y=map(int,raw_input().split())
y+=1
a=range(y)
print sum(i for i in[[i for a[::i]in[([0]*y)[::i]]][0]for i in a[2:]if a[i]]if i>=x)
\$\endgroup\$
1
  • \$\begingroup\$ You can remove y+=1 and instead use range(y+1) and ([0]*-~y)[::i] to save a byte (removing the newline). And using Python 3 will allow you to use input(), as long as you put parentheses after print, therefore removing 4 bytes, but adding 1. Worth it. \$\endgroup\$
    – mbomb007
    Commented Jun 26, 2015 at 21:54
0
\$\begingroup\$

F# (141)

One third of the code is for parsing the input.

let[|a;b|]=System.Console.ReadLine().Split(' ')
{int a..int b}|>Seq.filter(fun n->n>1&&Seq.forall((%)n>>(<>)0){2..n-1})|>Seq.sum|>printfn"%A"
\$\endgroup\$
0
\$\begingroup\$

Perl, 62 with bonus

use ntheory":all";while(<>){say vecsum(@{primes(split/\s+/)})}

Takes lines with two whitespace separated numbers and prints the sum of primes within the range. Exits when it sees EOF.

47 for the simple case we assume the input magically arrives in $a and $b like a few other solutions:

use ntheory":all";forprimes{$s+=$_}$a,$b;say$s

or

use ntheory":all";say vecsum(@{primes($a,$b)})

With a newer module version that can be 39 characters:

use ntheory":all";say sum_primes($a,$b)
\$\endgroup\$
0
\$\begingroup\$

Julia, 69 bytes

a,b=int(split(readline()));println(sum(setdiff(primes(b),primes(a))))

This reads a space-delimited pair of integers from STDIN and prints the result to STDOUT. The only thing I've really golfed here is whitespace; otherwise this is probably how I would go about it in a non-golfing context.

Ungolfed + explanation:

# Read a line from STDIN, split it into an array on the space, convert
# the elements to integers, and assign the first element to a and the
# second to b
a, b = int(split(readline()))

# Get the primes between a and b inclusive. primes(x) returns the primes
# <= x, so the set difference of primes(b) and primes(a) will get us only
# those between a and b
d = setdiff(primes(b), primes(a))

# Print the sum to STDOUT
println(sum(d))

Just realized how old this challenge is.

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

Scala, 260 bytes

object P extends App{
def c(M:Int)={val p=(false::false::true::List.range(3,M+1).map(_%2!=0)).toArray
for(i<-(3 to M)
if p(i))
{var j=i*i
while(j<M){p(j)=false
j+=i}}
p}
val l=args.map(_.toInt)
val p=c(l(1))
println((l(0)to l(1)).filter(p).map(_.toLong).sum)}

A self-written primes-sieve.

time scala P 3900000 4000000
25811704341

real    0m8.288s
user    0m6.968s
sys 0m0.456s
\$\endgroup\$
0
\$\begingroup\$

PowerShell, 94 bytes

$a,$b=$args[0,1]
(.{$p=2..$b
while($p){$p[0];$p=@($p|?{$_%$p[0]})}}|
?{$_-gt$a}|
measure -s).sum
\$\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.