Sum of primes between given range

Question

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 <= a <= b <= 10⁸

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. :)

Answer 1

J,^{41 32} 19 characters:

Update

(simple sieve)

g=:+/@(*1&p:)@-.&i.

e.g.

100 g 1
1060
250000x g 48
2623030823

Previous

h=:3 :'+/p:i.(_1 p:>:y)'
f=:-&h<:

eg:

100 f 1
1060

Answer 2

Mathematica 7 (31 chars in plain text)

If PARI/GP solution allowed, then:

Plus@@Select[Range[a,b],PrimeQ]

Answer 3

C (117 including NL)

main(a,b,s,j){
s=0,scanf("%d%d",&a,&b);
for(a+=a==1;a<=b;a++)
for(s+=a,j=2;j<a;)
s-=a%j++?0:(j=a);
printf("%d",s);
}

Answer 4

C# (294 characters):

using System;class P{static void Main(){int a=int.Parse(Console.ReadLine()),b=int.Parse(Console.ReadLine());long t=0;for(int i=a;i<=b;i++)if(p(i))t+=i;Console.WriteLine(t);}static bool p(int n){if((n%2<1&&n!=2)||n<2)return 0>1;for(int i=3;i<=Math.Sqrt(n);i+=2)if(n%i==0)return 0>1;return 1>0;}}

Answer 5

PARI/GP (44 characters)

sum(x=nextprime(a),precprime(b),x*isprime(x))

Answer 6

C#, 183 characters

using System;class P{static void Main(string[] a){long s=0,i=Math.Max(int.Parse(a[0]),2),j;for(;i<=int.Parse(a[1]);s+=i++)for(j=2;j<i;)if(i%j++==0){s-=i;break;}Console.WriteLine(s);}}

This would be much shorter if it didn't have to check for 1, or if there was a better way to... In a more readable format:

using System;
class P 
{ 
    static void Main(string[] a) 
    { 
        long s = 0,
             i = Math.Max(int.Parse(a[0]),2),
             j;

        for (; i <= int.Parse(a[1]);s+=i++)
            for (j = 2; j < i; )
                if (i % j++ == 0)
                {
                    s -= i;
                    break;
                }

        Console.WriteLine(s); 
    }
}

Answer 7

BASH Shell

47 Characters

seq 1 100|factor|awk 'NF==2{s+=$2}END{print s}'

Edit: Just realized the sum overflows and is coerced as a double.

52 50 Characters

Here's a bit longer solution, but handles overflows aswell

seq 1 100|factor|awk NF==2{print\$2}|paste -sd+|bc

Answer 8

Haskell (80)

c=u[2..];u(p:xs)=p:u[x|x<-xs,x`mod`p>0];s a b=(sum.filter(>=a).takeWhile(<=b))c

s 1 100 == 1060

Answer 9

Pari/GP (24 characters)

s=0;forprime(i=a,b,s+=i)

Like some other solutions, this doesn't strictly meet the requirements, as a and b aren't read from stdin or the command line. I thought it was a nice alternative to the other Pari/GP and Mathematica solutions however.

Answer 10

Ruby 1.9, 63 chars

require'prime';p=->a,b{Prime.each(b).select{|x|x>a}.inject(:+)}

Use like this

p[1,100] #=> 1060

Using the Prime class feels like cheating, but since the Mathematica solutions used built-in prime functions...

Answer 11

Perl, 62 chars

<>=~/\d+/;map$s+=$_*(1x$_)!~/^1$|(^11+)\1+$/,$&..$';print$s,$/

This one uses the prime number regex.

Answer 12

Normal Task (Python 3): 95 chars

a,b=map(int,input().split())
r=range
print(sum(1%i*all(i%j for j in r(2,i))*i for i in r(a,b+1)))

Bonus Task (Python 3): 119 chars

L=iter(map(int,input().split()))
r=range
for a,b in zip(L,L):print(sum(1%i*all(i%j for j in r(2,i))*i for i in r(a,b+1)))

Answer 13

R, 57 characters

a=scan();b=a[1]:a[2];sum(b[rowSums(!outer(b,b,`%%`))==2])

Answer 14

Japt, 7 bytes

òV fj x

Try it here.

Answer 15

Common Lisp: (107 chars)

(flet((p(i)(loop for j from 2 below i never (= (mod i j) 0))))(loop for x from(read)to(read)when(p x)sum x))

only works for starting points >= 1

Answer 16

APL (25 characters)

+/((R≥⎕)^~R∊R∘.×R)/R←1↓⍳⎕

This is a modification of a well-known idiom (see this page for an explanation) for generating a list of primes in APL.

Example:

      +/((R≥⎕)^~R∊R∘.×R)/R←1↓⍳⎕
⎕:
      100
⎕:
      1
1060

Answer 17

Factor -> 98

:: s ( a b -- n )
:: i ( n -- ? )
n 1 - 2 [a,b] [ n swap mod 0 > ] all? ;
a b [a,b] [ i ] filter sum ;

Output:

( scratchpad ) 100 1000 s

--- Data stack:
75067

Answer 18

05AB1E, 5 bytes

ŸDp*O

Try it online!

Ÿ      Push the list [a, ..., b]
 D     Push a duplicate of that list
  p    Replace primes with 1 and everything else with 0
   *   Element-wise multiply the two lists [1*0, 2*1, 3*1, 4*0, ...]
    O  Sum of the final list of primes

Answer 19

Python 3.1(153 chars):

from sys import*
p=[]
for i in range(int(argv[1]),int(argv[2])):
 r=1
 for j in range(2,int(argv[2])):
  if i%j==0and i!=j:r=0
 if r:p+=[i]
print(sum(p))

Answer 20

R (85 characters)

x=scan(nmax=2);sum(sapply(x[1]:x[2],function(n)if(n==2||all(n %% 2:(n-1)))n else 0))

Extremely inefficient! I'm pretty sure it takes O(n^2) time. It might give warnings about coercing a double to a logical.

Deobfuscated:

x <- scan(nmax=2)
start <- x[1]
end <- x[2]

#this function returns n if n is prime, otherwise it returns 0.
return.prime <- function(n) {
  # if n is 2, n is prime. Otherwise, if, for each number y between 2 and n, n mod y is 0, then n must be prime
  is.prime <- n==2 || all(n%% 2:(n-1))
  if (is.prime)
    n
  else
    0
} 
primes <- sapply(start:end, return.prime)
sum(primes)

Answer 21

In Q (95):

d:{sum s:{if[2=x;:x];if[1=x;:0];$[0=x mod 2;0;0=min x mod 2+til floor sqrt x;0;x]}each x+til y}

Sample Usage:

q)d[1;100]
1060

Answer 22

GolfScript, 27 24 bytes

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

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

Answer 23

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

Answer 24

C# 302

using System;namespace X{class B{static void Main(){long x=long.Parse(Console.ReadLine()),y=long.Parse(Console.ReadLine()),r=0;for(long i=x;i<=y;i++){if(I(i)){r+=i;}}Console.WriteLine(r);}static bool I(long n){bool b=true;if(n==1){b=false;}for(long i=2;i<n;++i){if(n%i==0){b=false;break;}}return b;}}}

Answer 25

Mathematica, 27

Predefined a and b:

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

As a function (also 27):

Tr[Range@##~Select~PrimeQ]&

Answer 26

133 chars, Lua (no is_prime in-built function)

for i=m,n,1 do
if i%2~=0 and i%3~=0 and i%5~=0 and i%7~=0 and i%11~=0 then
s=s+1
end
end
print(s)

Here's an example where I added the line "print(i)" to display all primes found and the sum at the end of them: http://codepad.org/afUvYHnm.

Answer 27

PowerShell - 94

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

Answer 28

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.

Answer 29

Jelly, 3 bytes

æRS

Try it online!

Answer 30

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

Answer 31

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"

Answer 32

Scala: 260

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

Answer 33

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)

Answer 34

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)

Answer 35

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.

Answer 36

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

Answer 37

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.

Answer 38

Python: 110 chars

l,h=map(int,raw_input().split())
print sum(filter(lambda p:p!=1 and all(p%i for i in range(2,p)),range(l,h)))

Answer 39

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.

Answer 40

Java 7, 239 237 bytes

class M{public static void main(String[]a){c(new Long(a[0]),new Long(a[1]));}static void c(long a,long b){long r=0,i=a-1;for(;++i<=b;r+=p(i)?i:0);System.out.print(r);}static boolean p(long n){int i=2;while(i<n)n=n%i++<1?0:n;return n>1;}}

Ungolfed & test case:

class M{
  static void c(long a,long b){
    long r = 0,
         i = a-1;
    for(; ++i <= b; r += p(i) ? i : 0);
    System.out.print(r);
  }

  public static void main(String[] a){
    c(new Long(a[0]), new Long(a[1]));
  }

  static boolean p(long n){
    int i = 2;
    while(i < n){
      n = n % i++ < 1 ? 0 : n;
    }
    return n > 1;
  }
}

Usage: java -jar M.jar 5 17
Output: 53

Answer 41

Haskell, 47 44 bytes

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

SEJPM helped me save 3 bytes!

Answer 42

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