Jumlah bilangan prima antara rentang yang diberikan

27

Tulis kode terpendek untuk menemukan jumlah bilangan prima di antara adan b(termasuk).

Memasukkan

  1. adan bdapat diambil dari command line atau stdin (spasi terpisah)
  2. Asumsikan 1 <= a <= b <=10 8

Keluaran Cukup cetak jumlah dengan karakter baris baru.

Poin Bonus

  1. Jika program menerima beberapa rentang (cetak satu jumlah pada setiap baris), Anda mendapatkan poin tambahan. :)
st0le
sumber
Batas atas terlalu besar untuk memungkinkan banyak solusi menarik (jika mereka harus menyelesaikan dalam waktu yang masuk akal, setidaknya).
hallvabo
@hallvabo Anda menemukan solusi tidak efisien menarik?
Matius Baca
@hallvabo, Tidak apa-apa. Saya tidak berpikir ada yang keberatan solusi yang tidak efisien. Jika objek lain, saya akan sangat senang untuk menurunkan batas
st0le
Baru saja membuat dan menjalankan versi program yang tidak terlalu dioptimalkan atau ringkas dalam C #, menggunakan 1 hingga 10 ^ 8. Dengan asumsi algoritma saya benar, itu berjalan di bawah 1m30s, dan tidak meluap dari waktu yang lama. Sepertinya batas atas baik untuk saya!
Nellius
Pemeriksaan cepat dan mudah: jumlah bilangan prima antara 1 dan 100 = 1060.
Nellius

Jawaban:

15

J, 41 32 19 karakter:

Memperbarui

(ayakan sederhana)

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

misalnya

100 g 1
1060
250000x g 48
2623030823

Sebelumnya

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

misalnya:

100 f 1
1060
Eelvex
sumber
11

Mathematica 7 (31 karakter dalam teks biasa)

Jika solusi PARI / GP diizinkan, maka:

Plus@@Select[Range[a,b],PrimeQ]
Nakilon
sumber
Apa maksudmu PARI / GP dan Mathematica adalah bahasa pemrograman yang bagus.
Eelvex
@Eelvex, tidak, mereka melanggar salah satu aturan golf: menggunakan fungsi tingkat tinggi khusus bawaan .
Nakilon
Saya tidak berpikir ada aturan seperti itu . Masih merupakan masalah terbuka kapan harus menggunakan fungsi tingkat tinggi. Lihat misalnya. pertanyaan meta ini
Eelvex
1
28 karakter Range[a,b]~Select~PrimeQ//Tr.
chyanog
6

C (117 termasuk 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);
}
Alexandru
sumber
5

C # (294 karakter):

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;}}
Nellius
sumber
Anda dapat membuat semua Anda ints longdan menyimpan beberapa karakter: long a=...,b=...,t=0,i=a;for(;i<=b;i++). Ini membuatnya menjadi 288 karakter. Anda juga dapat membiarkan pkembali lama dan hanya mengembalikan salah satu 0atau ndan memperpendek loop ke t+=p(i). 277 karakter, kalau begitu.
Joey
5

PARI / GP (44 karakter)

sum(x=nextprime(a),precprime(b),x*isprime(x))
Eelvex
sumber
6
Bukankah seharusnya pemilih memberikan alasan untuk -1 mereka?
Eelvex
Downvote mungkin untuk menggunakan built-in.
mbomb007
4

BASH Shell

47 Karakter

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

Sunting: Baru menyadari jumlah kelebihan dan dipaksa sebagai ganda.

52 50 Karakter

Ini solusi yang sedikit lebih lama, tetapi juga menangani luapan

seq 1 100|factor|awk NF==2{print\$2}|paste -sd+|bc
st0le
sumber
tr lebih pendek dari tempel, dan Anda dapat menghapus tanda kutip tunggal (lolos dari $).
Nabb
@Nabb, akan memperbaikinya segera setelah saya mendapatkan kotak * nix, atau Anda dapat melakukan penghormatan.
st0le
@Nabb, tidak bisa berfungsi, trmenambahkan tanda '+' di akhir, memperbaikinya akan membutuhkan lebih banyak karakter.
st0le
Ah, ketinggalan itu. Meskipun saya pikir Anda masih dapat mengubah untuk awk NF==2{print\$2}menyimpan byte pada solusi yang lebih lama (kami tidak akan sengaja mengalami ekspansi brace karena tidak ada koma atau ..s).
Nabb
@Nabb, kamu benar. Selesai :)
st0le
4

C #, 183 karakter

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);}}

Ini akan menjadi jauh lebih pendek jika tidak harus memeriksa 1, atau jika ada cara yang lebih baik untuk ... Dalam format yang lebih mudah dibaca:

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); 
    }
}
Nick Larsen
sumber
Saya suka betapa singkatnya ini, tetapi saya bertanya-tanya seberapa tidak efisiennya jika menghitung hingga 10 ^ 8!
Nellius
Benar, tetapi efisiensi tidak ada dalam aturan!
Nick Larsen
Anda tahu penyusun angka numerik default ke 0 kan? Itu akan menyelamatkan Anda beberapa karakter lagi di sana
jcolebrand
Memberikan kesalahan saat dikompilasi tanpa itu
Nick Larsen
... karena tidak pernah ditugaskan sebelum digunakan (via s -= i;karena itu hanya gula sintaksis s = s - i;yang mencoba mengakses ssebelum menyetelnya)
Nick Larsen
3

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

Ming-Tang
sumber
Ini golf kode! Mengapa Anda menggunakan nama panjang seperti itu untuk barang-barang Anda?
FUZxxl
4
Sulit menemukan nama yang lebih pendek daripada c, u, s ... Selebihnya adalah perpustakaan standar bahasa.
JB
3

Ruby 1.9, 63 karakter

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

Gunakan seperti ini

p[1,100] #=> 1060

Menggunakan Primekelas terasa seperti curang, tetapi karena solusi Mathematica menggunakan fungsi-fungsi utama bawaan ...

Michael Kohl
sumber
3

Perl, 62 karakter

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

Yang ini menggunakan bilangan prima regex.

ninjalj
sumber
3

Tugas Normal (Python 3): 95 karakter

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

Tugas Bonus (Python 3): 119 karakter

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)))
jamylak
sumber
3

Pari / GP (24 karakter)

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

Seperti beberapa solusi lain, ini tidak sepenuhnya memenuhi persyaratan, karena adan btidak dibaca dari stdin atau baris perintah. Saya pikir itu adalah alternatif yang bagus untuk solusi Pari / GP dan Mathematica lainnya.

DanaJ
sumber
1
+1: Ini adalah cara saya benar-benar melakukannya, bahkan tanpa bermain golf.
Charles
2

Gangguan Umum: (107 karakter)

(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))

hanya berfungsi untuk titik awal> = 1

tobyodavies
sumber
2

APL (25 karakter)

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

Ini adalah modifikasi dari idiom terkenal (lihat halaman ini untuk penjelasan) untuk menghasilkan daftar bilangan prima di APL.

Contoh:

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

Faktor -> 98

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

Keluaran:

( scratchpad ) 100 1000 s

--- Data stack:
75067
defhlt
sumber
2

R, 57 karakter

a=scan();b=a[1]:a[2];sum(b[rowSums(!outer(b,b,`%%`))==2])
plannapus
sumber
Apakah n=2perlu menyebutkan scan()? Jika input standar, apakah ada masalah dengan menghilangkan argumen dan menganggap <enter> ekstra diperlukan?
Gaffi
1
Tidak, sebenarnya Anda benar, saya bisa melakukannya tanpa. Itu murni karena alasan estetika (karena saya tahu kode saya bukan yang terpendek :))
plannapus
Yah, +1 dari saya sama saja, karena jelas bukan yang terpanjang.
Gaffi
2

Japt , 7 byte

òV fj x

Coba di sini.

Erik the Outgolfer
sumber
Selamat datang di Japt :)
Shaggy
@ Shaggy Saya awalnya mencoba untuk menemukan "prime range" builtin di Japt, tetapi kemudian memutuskan untuk menerima tantangan: p
Erik the Outgolfer
Mengingat berapa banyak tantangan yang terkait dengan bilangan prima, jalan pintas untuk fj<space>bisa berguna.
Shaggy
1

Perl, 103 karakter

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

Ini akan menerima beberapa garis yang dipisahkan spasi dan memberikan jawaban untuk masing-masing: D

pengecut anonim
sumber
1

Di 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}

Penggunaan sampel:

q)d[1;100]
1060
sinedcm
sumber
1

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;}}}
Saumil
sumber
1

Mathematica , 27

Telah ditentukan sebelumnya adan b:

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

Sebagai fungsi (juga 27):

Tr[Range@##~Select~PrimeQ]&
Tuan Penyihir
sumber
1

R (85 karakter)

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

Sangat tidak efisien! Saya cukup yakin ini membutuhkan waktu O (n ^ 2). Mungkin memberi peringatan tentang memaksa ganda untuk logis.

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)
raptortech97
sumber
1

Python 3.1 (153 karakter):

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))
John
sumber
1. from sys import*2. r=True-> r=1(dan masing 0- masing untuk False) 3. if i%j==0and i!=j:r=04. if r:p+=[i]5. print(sum(p))(menggantikan 4 baris terakhir)
seequ
Anda bisa menggunakan input()untuk menjadi lebih pendek. Juga, bisakah Anda menggunakan if i%j<1andsebagai gantinya?
mbomb007
1

05AB1E , 5 byte

ŸDp*O

Cobalah 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
Galoubet
sumber
0

Python: 110 karakter

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)))
zxul767
sumber
Ini tidak termasuk.
jamylak
0

Python, 133

Sedikit ilmu sihir:

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)
JBernardo
sumber
-1 (Yah saya belum punya cukup rep untuk downvote) Ini tidak valid dalam Python 2 atau 3, Anda tidak bisa mengharapkan input dengan mudah berisi tanda kutip untuk Anda. Ubah ke raw_input atau gunakan python 3 plz
jamylak
Anda dapat menghapus y+=1dan sebagai gantinya menggunakan range(y+1)dan ([0]*-~y)[::i]untuk menyimpan byte (menghapus baris baru). Dan menggunakan Python 3 akan memungkinkan Anda untuk menggunakan input(), selama Anda menempatkan tanda kurung setelahnya print, karena itu menghapus 4 byte, tetapi menambahkan 1. Worth it.
mbomb007
0

133 chars, Lua (tidak ada fungsi is_prime built-in)

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)

Berikut ini adalah contoh di mana saya menambahkan baris "cetak (i)" untuk menampilkan semua bilangan prima yang ditemukan dan jumlahnya di bagian akhir: http://codepad.org/afUvYHnm .

pengguna8524
sumber
"A dan b dapat diambil dari baris perintah atau stdin" Di mana dari dua cara mana angka-angka dapat diteruskan ke kode Anda?
manatwork
1
Menurut ini 13 (apa pun di atasnya) bukan bilangan prima.
st0le
@ st0le Menurut logika 13 adalah "prima" (tetapi misalnya 2 tidak) - di sisi lain 13 * 13 = 169 adalah "prima" lagi ...
Howard
0

PowerShell - 94

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

F # (141)

Sepertiga dari kode adalah untuk mem-parsing 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"
Ming-Tang
sumber