27
\$\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 <= a <= b <= 108

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\$
  • \$\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
  • \$\begingroup\$ @hallvabo You find inefficient solutions interesting? \$\endgroup\$ – Matthew Read 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

42 Answers 42

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

PARI/GP (44 characters)

sum(x=nextprime(a),precprime(b),x*isprime(x))
\$\endgroup\$
  • 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\$

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\$
  • \$\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
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\$
  • \$\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\$ – Nick Larsen 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\$ – Nick Larsen 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\$ – Nick Larsen Jan 29 '11 at 21:28
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\$
  • \$\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\$

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

Perl, 62 chars

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

This one uses the prime number regex.

\$\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
    \$\begingroup\$ +1: This is the way I'd actually do it, even without golfing. \$\endgroup\$ – Charles Apr 28 '15 at 14:55
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 >= 1

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

R, 57 characters

a=scan();b=a[1]:a[2];sum(b[rowSums(!outer(b,b,`%%`))==2])
\$\endgroup\$
  • \$\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
\$\begingroup\$

Japt, 7 bytes

òV fj x

Try it here.

\$\endgroup\$
  • \$\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\$ – Erik the Outgolfer Oct 11 '17 at 12:01
  • \$\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
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\$

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

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

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

GolfScript, 27 24 bytes

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

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

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

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)))
\$\endgroup\$
  • \$\begingroup\$ This is not inclusive. \$\endgroup\$ – jamylak Jul 30 '12 at 6:23
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\$
  • \$\begingroup\$ -1 (Well I don't have enough rep to downvote yet) This is invalid in Python 2 or 3, you can't expect input to conveniently contain quotation marks for you. Change to raw_input or use python 3 plz \$\endgroup\$ – jamylak Jul 30 '12 at 6:21
  • \$\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 Jun 26 '15 at 21:54
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ “a and b can be taken from command line or stdin” In which of those two ways can the numbers be passed to your code? \$\endgroup\$ – manatwork Jul 7 '13 at 10:41
  • 1
    \$\begingroup\$ According to this 13 (anything over it) is not a prime number. \$\endgroup\$ – st0le Jul 7 '13 at 16:53
  • \$\begingroup\$ @st0le According to the logic 13 is a "prime" (but e.g. 2 is not) - on the other hand 13*13 = 169 is "prime" again... \$\endgroup\$ – Howard Jul 8 '13 at 11:30
0
\$\begingroup\$

PowerShell - 94

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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