30
\$\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
    Jan 28 '11 at 9:13
  • 1
    \$\begingroup\$ @hallvabo You find inefficient solutions interesting? \$\endgroup\$ Jan 28 '11 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
    Jan 28 '11 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
    Jan 28 '11 at 12:08
  • \$\begingroup\$ A quick easy check: sum of primes between 1 and 100 = 1060. \$\endgroup\$
    – Nellius
    Jan 28 '11 at 12:50

51 Answers 51

15
\$\begingroup\$

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
\$\endgroup\$
11
\$\begingroup\$

Mathematica 7 (31 chars in plain text)

If PARI/GP solution allowed, then:

Plus@@Select[Range[a,b],PrimeQ]
\$\endgroup\$
4
  • \$\begingroup\$ What's your point? PARI/GP and Mathematica are fine programming languages. \$\endgroup\$
    – Eelvex
    Jan 29 '11 at 8:28
  • \$\begingroup\$ @Eelvex, no, they break one of golf rules: using built-in specific highlevel functions. \$\endgroup\$
    – Nakilon
    Jan 29 '11 at 9:19
  • \$\begingroup\$ I don't think there is such a rule. It's still an open matter when to use highlevel functions. See for ex. this meta question \$\endgroup\$
    – Eelvex
    Jan 29 '11 at 9:42
  • 1
    \$\begingroup\$ 28 chars Range[a,b]~Select~PrimeQ//Tr. \$\endgroup\$
    – chyanog
    Sep 9 '13 at 5:12
6
\$\begingroup\$

C, 117 bytes

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);
}
\$\endgroup\$
5
\$\begingroup\$

PARI/GP, 44 characters

sum(x=nextprime(a),precprime(b),x*isprime(x))
\$\endgroup\$
2
  • 6
    \$\begingroup\$ Shouldn't down voters give a reason for their -1? \$\endgroup\$
    – Eelvex
    Jan 29 '11 at 8:27
  • \$\begingroup\$ The downvote was probably for using built-ins. \$\endgroup\$
    – mbomb007
    Jun 26 '15 at 21:48
5
\$\begingroup\$

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;}}
\$\endgroup\$
1
  • \$\begingroup\$ You can make all your ints long and save a few characters: long a=...,b=...,t=0,i=a;for(;i<=b;i++). This gets it to 288 chars. You can also let p return a long and just return either 0 or n and shorten the loop to t+=p(i). 277 chars, then. \$\endgroup\$
    – Joey
    Jun 19 '11 at 9:28
4
\$\begingroup\$

Perl, 62 chars

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

This one uses the prime number regex.

\$\endgroup\$
4
\$\begingroup\$

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); 
    }
}
\$\endgroup\$
7
  • \$\begingroup\$ I like how short this is, but I wonder how inefficient it would be when calculating up to 10^8! \$\endgroup\$
    – Nellius
    Jan 28 '11 at 17:24
  • \$\begingroup\$ True, but efficiency wasn't in the rules! \$\endgroup\$ Jan 28 '11 at 18:20
  • \$\begingroup\$ You know the compiler defaults numerics to 0 right? That'ld save you a couple more chars in there \$\endgroup\$
    – jcolebrand
    Jan 29 '11 at 6:20
  • \$\begingroup\$ Gives error when compiled without it \$\endgroup\$ Jan 29 '11 at 21:21
  • \$\begingroup\$ ...because it is never assigned before it is used (via s -= i; because thats just syntactic sugar for s = s - i; which tries to access s before setting it) \$\endgroup\$ Jan 29 '11 at 21:28
4
\$\begingroup\$

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
\$\endgroup\$
5
  • \$\begingroup\$ tr is shorter than paste, and you can remove the single quotes (escape the $). \$\endgroup\$
    – Nabb
    Feb 4 '11 at 4:25
  • \$\begingroup\$ @Nabb, will fix it as soon as i get my hands on a *nix box, or you could do the honours. \$\endgroup\$
    – st0le
    Feb 4 '11 at 4:28
  • \$\begingroup\$ @Nabb, can't get it to work, tr adds a trailing '+' at the end, fixing it will take more chars. \$\endgroup\$
    – st0le
    Feb 6 '11 at 11:47
  • \$\begingroup\$ Ah, missed that. Although I think you can still change to awk NF==2{print\$2} to save a byte on the longer solution (we won't accidentally run into brace expansion because there are no commas or ..s). \$\endgroup\$
    – Nabb
    Feb 6 '11 at 19:29
  • \$\begingroup\$ @Nabb, you're right. Done :) \$\endgroup\$
    – st0le
    Feb 7 '11 at 4:25
3
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ This is code-golf! Why do you use such long names for your stuff? \$\endgroup\$
    – FUZxxl
    Feb 3 '11 at 16:30
  • 4
    \$\begingroup\$ It's hard to find shorter names than c, u, s... The rest is language standard library. \$\endgroup\$
    – J B
    Feb 7 '11 at 10:04
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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)))
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ +1: This is the way I'd actually do it, even without golfing. \$\endgroup\$
    – Charles
    Apr 28 '15 at 14:55
3
\$\begingroup\$

Japt, 7 bytes

òV fj x

Try it here.

\$\endgroup\$
3
  • \$\begingroup\$ Welcome to Japt :) \$\endgroup\$
    – Shaggy
    Oct 11 '17 at 12:00
  • \$\begingroup\$ @Shaggy I originally tried to find a "prime range" builtin in Japt, but then decided to accept the challenge :p \$\endgroup\$ Oct 11 '17 at 12:01
  • 1
    \$\begingroup\$ Given how many challenges there are related to primes, a shortcut for fj<space> could be handy. \$\endgroup\$
    – Shaggy
    Oct 11 '17 at 12:02
3
\$\begingroup\$

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

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

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
\$\endgroup\$
2
\$\begingroup\$

Jelly, 3 bytes

æRS

Try it online!

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

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
\$\endgroup\$
2
  • \$\begingroup\$ ✓ I didn't think of using p* \$\endgroup\$
    – Someone
    Jan 3 at 17:00
  • \$\begingroup\$ More boring solution with filter: Ÿʒp}O \$\endgroup\$
    – Makonede
    Apr 17 at 18:09
2
\$\begingroup\$

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

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

R, 57 characters

a=scan();b=a[1]:a[2];sum(b[rowSums(!outer(b,b,`%%`))==2])
\$\endgroup\$
3
  • \$\begingroup\$ Is specifying n=2 necessary in scan()? If the input is standard, is there a problem with omitting the argument and assuming an extra <enter> is required? \$\endgroup\$
    – Gaffi
    Oct 30 '13 at 19:16
  • 1
    \$\begingroup\$ No actually you're right I could have done without. It was purely for aesthetic reasons (since i knew my code wasn't the shortest anyway :) ) \$\endgroup\$
    – plannapus
    Oct 30 '13 at 19:26
  • \$\begingroup\$ Well, +1 from me just the same, as it's definitely not the longest. \$\endgroup\$
    – Gaffi
    Oct 30 '13 at 19:27
2
+50
\$\begingroup\$

Factor + math.primes math.unicode, 32 23 bytes

[ primes-between Σ . ]

-9 bytes thanks to chunes!

Try it online!

\$\endgroup\$
3
  • 1
    \$\begingroup\$ prime? and Σ are not available by default, so you need to change the header to "Factor + math.primes math.unicode" like this. \$\endgroup\$
    – Bubbler
    Mar 14 at 23:27
  • \$\begingroup\$ Thank you, @Bubbler I changed the header of my answers :) \$\endgroup\$ Mar 14 at 23:59
  • 1
    \$\begingroup\$ primes-between is shorter than [a,b] [ prime? ] filter. \$\endgroup\$
    – chunes
    Apr 17 at 16:09
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\$

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
\$\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.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))
\$\endgroup\$
2
  • \$\begingroup\$ 1. from sys import* 2. r=True -> r=1 (and respectively 0 for False) 3. if i%j==0and i!=j:r=0 4. if r:p+=[i] 5. print(sum(p)) (replaces last 4 lines) \$\endgroup\$
    – seequ
    Aug 7 '14 at 21:13
  • \$\begingroup\$ You can use input() to be shorter. Also, can you use if i%j<1and instead? \$\endgroup\$
    – mbomb007
    Jun 26 '15 at 21:51
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\$

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
    Jan 3 at 21:08
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\$

C#, 302 bytes

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

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

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .