Temukan Fibonnaci Prime, dalam kode terpendek

8

Tantangannya agak sederhana:

  1. Ambil bilangan bulat positif nsebagai masukan.
  2. Keluarkan nangka utama Fibonacci.

Input dapat sebagai parameter untuk suatu fungsi (dan output akan menjadi nilai balik), atau dapat diambil dari baris perintah (dan dikeluarkan di sana).

Catatan: Menggunakan fungsi pengecekan bawaan atau generator seri Fibonacci tidak diperbolehkan.

Semoga berhasil!

Inkbug
sumber
1
kemungkinan duplikat dari fungsi atau urutan Fibonacci
Keith Randall
1
Apakah ada batasan ukuran?
MrZander
@ MrZander Ukuran apa?
Inkbug
Ukuran input / output. Apakah saya perlu memperhitungkan prime_fib (1000000000000000000)? Dimana batasannya?
MrZander
@ MrZander Algoritme harus mendukung angka besar yang sewenang-wenang, tetapi fungsinya dapat meningkatkan pengecualian di luar batas jika hasilnya terlalu besar untuk int normal.
Inkbug

Jawaban:

2

Ruby, 55

f=->n,a=1,b=2{n<1?a:f[n-(2..b).find{|f|b%f<1}/b,b,a+b]}

Panggilan sendiri secara rekursif, melacak dua angka terakhir dalam urutan Fibonacci di adan b, dan berapa banyak bilangan prima yang dilihatnya sejauh ini n. nakan dikurangi ketika faktor terkecil lebih besar dari 1 b, dibagi dengan bdan dibulatkan ke bilangan bulat terdekat, adalah 1 daripada 0, yang terjadi hanya untuk prime b. Ketika itu terlihat semua bilangan prima yang seharusnya, itu mencetak a, yang merupakan yang paling baru bdiuji untuk primality.

histokrat
sumber
4

C, 66

f(n,a,b){int i=2;while(a%i&&i++<a);return(n-=i==a)?f(n,b,a+b):a;}

Gautam
sumber
2
Saya pikir Anda harus menentukan nilai awal adan bdi dalam fungsi Anda.
defhlt
Bukankah untuk loop lebih pendek? (Saya tidak tahu C dengan baik)
Inkbug
1
Dapat dikurangi menjadi 65 karakter: f(n,a,b){int i=2;while(a%i&&i++<a);return(n-=i==a)?f(n,b,a+b):a;}- @ArtemIce: a= 1 dan b= 2 bekerja untuk saya.
schnaader
2
@ schnaader tentu saja mereka bekerja, tetapi kode yang menetapkan a & b harus dihitung karena itu codegolf
defhlt
3
Tidak memiliki kode inisialisasi untuk a & b ... Jadi bisakah Anda memperbaiki hanya dengan menambahkan g(n){f(n,1,2);}?
bayi-kelinci
3

C, 85 , 81 , 76

f(n){int i=1,j=0,k;for(;n;n-=k==i)for(j=i-j,i+=j,k=2;i%k&&k++<i;);return i;}
  • meminjam gaya kode cek bilangan prima sederhana dari @Gautam

  • fungsi C mandiri (tidak ada global)

Pengujian:

main(int n,char**v){printf("%d\n",f(atoi(v[1])));}

./a.out 10
433494437

./a.out 4
13
bayi-kelinci
sumber
2

Mathematica, 59 atau 63 byte

(a=b=1;Do[While[{a,b}={b,a+b};Length@Divisors@b>2],{#}];b)&
(a=b=1;Do[While[{a,b}={b,a+b};b~Mod~Range@b~Count~0>2],{#}];b)&

Ini adalah fungsi yang tidak disebutkan namanya yang mengambil ninput mereka dan mengembalikan prime Fibonacci yang benar. Versi yang lebih pendek menggunakan Divisors. Saya tidak sepenuhnya yakin apakah ini diperbolehkan, tetapi jawaban Mathematica lainnya bahkan digunakan FactorInteger.

Yang kedua tidak menggunakan fungsi-fungsi terkait factorisation sama sekali, melainkan menghitung jumlah bilangan bulat lebih kecil dari nyang menghasilkan 0dalam operasi modulo. Bahkan versi ini mengalahkan semua pengiriman yang valid, tetapi saya yakin hanya memposting jawaban ini akan menyebabkan beberapa orang memberikan jawaban kompetitif dalam GolfScript, APL atau J.;)

Martin Ender
sumber
1

Mathematica 147 143 141 141 karakter

f@0 = 0; f@1 = 1; f@n_ := f[n - 1] + f[n - 2]
q@1 = False; q@n_ := FactorInteger@n~MatchQ~{{_, 1}}
p = {}; k = 1; While[Length@p < n, If[q@f@k, p~AppendTo~f[k]]; k++];p[[-1]]

f adalah definisi berulang dari angka Fibonacci.

q mendeteksi bilangan prima.

kadalah Fibonacci prime iff q@f@kBenar.

Untuk n= 10, output adalah 433494437.

DavidC
sumber
oh tuhan, induksi ...: gemetar:
acolyte
@acolyte Sangat menyenangkan untuk melihat jejak fungsi yang memanggil dirinya sendiri.
DavidC
Orang: Itu adalah salah satu kursus yang menegaskan saya perlu untuk mendapatkan frak dari CompSci.
acolyte
1

Ruby, 94 68 67

n=->j{a=b=1
while j>0
a,b=b,a+b
(2...b).all?{|m|b%m>0}&&j-=1
end
b}





Clojure, 112

Tidak Disatukan:

(defn nk [n]
  (nth 
    (filter
      (fn[x] (every? #(> (rem x %) 0) (range 2 x)))    ; checks if number is prime
      ((fn z[a b] (lazy-seq (cons a (z b (+ a b))))) 1 2)) ; Fib seq starting from [1, 2]
    n)) ; get nth number

Golf: (defn q[n](nth(filter(fn[x](every? #(>(rem x %)0)(range 2 x)))((fn z[a b](lazy-seq(cons a(z b(+ a b)))))2 3))n))

defhlt
sumber
1

Haskell 108

p=2 : s [3,5..]  where
    s (p:xs) = p : s [x|x<-xs,rem x p /= 0]
f=0:1:(zipWith (+) f$tail f)
fp=intersect p f

Untuk mendapatkan nnomor panggil saja fp !! n.

EDIT: Sic. Jawaban yang salah, saya memperbaikinya.

Hauleth
sumber
0

Groovy: 105 (134 dengan spasi putih)

b adalah fungsi fibonacci.

penutupan di dalam if adalah fungsi pemeriksaan prima. Perbarui: perbaikan kecil di atasnya

r adalah nomor fibonacci utama.

r={ n->
  c=k=0
  while(1) {
    b={a->a<2?a:b(a-1)+b(a-2)}
    f=b k++
    if({z->z<3?:(2..<z).every{z%it}}(f)&&c++==n)return f
  }
}

Kasus uji:

assert r(0) == 0
assert r(1) == 1
assert r(2) == 1
assert r(3) == 2
assert r(4) == 3
assert r(5) == 5
assert r(6) == 13
assert r(7) == 89
assert r(8) == 233
assert r(9) == 1597

Versi yang dapat dibaca:

def fib(n) { 
  n < 2 ? n : fib(n-1) + fib(n-2)
}
def prime(n) {
  n < 2 ?: (2..<n).every { n % it }
}
def primeFib(n) { 
  primes = inc = 0
  while( 1 ) {
    f = fib inc++
    if (prime( f ) && primes++ == n) return f
  }
}
Will Lp
sumber
0

C, 105 (dengan spasi)

Implementasi fibonacci menggunakan pemrograman dinamis:

long f(int n){int i;long b2=0,b1=1,n;if(n)return 0;for(i=2;i<n;i++){n=b1+b2;b2=b1;b1=n;}return b1+b2;}

Kode yang dapat dibaca:

long f(int n)
{
  int i;
  long back2 = 0, back1 = 1;
  long next;

  if ( n == 0 ) return 0;

  for ( i=2; i<n; i++ )
  {
    next  = back1 + back2;
    back2 = back1;
    back1 = next;
  }

  return back1 + back2;
}
elp
sumber
Bagaimana ini dapat memiliki 1 suara? Tidak menjawab pertanyaan (tidak ada pemeriksaan awal) dan versi singkatnya bahkan tidak dapat dikompilasi
edc65
0

Pyth - 29 byte

Loops Fibonacci hingga array adalah panjang n tetapi hanya menambah array jika prime.

J2K1W<lYQAJK,+KJJI!tPK~Y]K;eY

Agak lambat, tetapi mencapai n = 10 dalam ~ 15 detik. Mungkin bisa bermain golf lebih banyak.

J2              J=2
K1              K=1
W        <lYQ   While length of array<input
 AJK,+KJJ       J,K=K+J,J
 I!tPK          If K prime(not builtin prime function, uses prime factorization)
  ~Y]K          append K to Y
;               End loop so next is printed
eY              last element of Y
Penafian: Pyth lebih baru dari tantangan ini, jadi tidak bersaing.
Maltysen
sumber
-1

Javascript:

Number.prototype.fiboN = function()
{
var r = (Math.pow((1 + Math.sqrt(5)) / 2,this) - (Math.pow(1 - (1 + Math.sqrt(5)) / 2,this))) / Math.sqrt(5);
return r.toFixed(0);
}

alert((10).fiboN()); // = 55 assuming the serie starts with 1,1,2,3,5,8,13,...
alert((46).fiboN()); // = 1836311903
Jón Jónsson
sumber
Tidak menjawab pertanyaan - 55 bukan Perdana. Namun, senang Anda menggunakan Rasio Emas itu.
Jacob