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

1
2
1
\$\begingroup\$

Vyxal, 5 4 bytes, s

ræT›

Try it!

Explanation

r    # Range a to b (input)
æ    # Map prime check
T    # Indices of truthy values
›    # Increment

Then s flag sums the stack.

-1 thanks to @Lyxal

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

C (clang), 164 138 122 bytes

i,x,y,z;main(f){for(scanf("%d %d",&x,&y);x<y;z+=x++*!f)if(f=0,x<2)++x;else for(i=2;x/2/i&&!(f|=x%i++<1););printf("%i",z);}

Try it online!

Original code from Programiz. Just modified the code to reduce bytes. Yes, I'm terrible at this.

Code changed thanks to Pedro Maimere, byte count didn't change. Thanks to ceilingcat for golfing 26 bytes, and another 16 bytes.

\$\endgroup\$
1
  • \$\begingroup\$ As is, your code is not adding y, if prime. You have to use while(x<=y) instead, adding one byte. On the other side, you can omit one space here: "%d %d".Try it online! \$\endgroup\$ Jun 2 at 12:52
1
\$\begingroup\$

Factor + math.primes, 37 bytes

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

Try it online!

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

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

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

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

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

\$\endgroup\$
0
\$\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\$
0
\$\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
    Oct 11 '17 at 12:00
  • \$\begingroup\$ Fails for 1!3 (gives 6 instead of 5).. \$\endgroup\$ Aug 9 '18 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
    Oct 19 '20 at 15:48
0
\$\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\$
0
\$\begingroup\$

Desmos, 124 bytes

I know this is a long time ago, but I'm bored :).

f(a,b)=\sum_{n=a}^b\left\{\prod_{k=2}^{n-1}\left\{\operatorname{mod}(n,k)=0:0,1\right\}-\left\{n<2:1,0\right\}=1:n,0\right\}

Try it on Desmos!

I had to waste 23 bytes just for the edge case of 0 and 1(-\left\{n<2:1,0\right\}). I feel like this could definitely be golfed further, but I'm not that skilled at Desmos. I especially think that the edge cases 0 and 1 could be handled a lot better than what I'm doing currently.

\$\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\$
0
\$\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
    Jul 30 '12 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\$ Oct 16 '20 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
    Oct 16 '20 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\$ Oct 17 '20 at 23:19
0
\$\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\$
0
\$\begingroup\$

Python 3.8 (pre-release), 95 bytes

a,b=map(int,input().split());print(sum(n for n in range(a,b+1)if all(n%i for i in range(2,n))))

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ Invalid. This considers \$1\$ as a prime number. \$\endgroup\$
    – Makonede
    Jun 2 at 18:34
0
\$\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
2

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.