Fibonacci Baba

This kills the problem.

Trial division is not the best prime test especially if the numbers are very large. I used Miller-Rabin primality test.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

import random
import sys

def prime(n, k = 7):
   """use Rabin-Miller algorithm to return True (n is probably prime)
      or False (n is definitely composite)"""
   if n < 6:  # assuming n >= 0 in all cases... shortcut small cases here
      return [False, False, True, True, False, True][n]
   elif n & 1 == 0:  # should be faster than n % 2
      return False
   else:
      s, d = 0, n - 1
      while d & 1 == 0:
         s, d = s + 1, d >> 1
      # Use random.randint(2, n-2) for very large numbers
      for a in random.sample(xrange(2, min(n - 2, sys.maxint)), min(n - 4, k)):
         x = pow(a, d, n)
         if x != 1 and x + 1 != n:
            for r in xrange(1, s):
               x = pow(x, 2, n)
               if x == 1:
                  return False  # composite for sure
               elif x == n - 1:
                  a = 0  # so we know loop didn't continue to end
                  break  # could be strong liar, try another a
            if a:
               return False  # composite if we reached end of this loop
      return True  # probably prime if reached end of outer loop

a = 1
b = 1

count = 0

while count < 15:
    a += b
    b += a

    count += prime(a) + prime(b)

print a if count == 15 else b

Output -

1

475420437734698220747368027166749382927701417016557193662268716376935476241

Length is 75.

The prime test doesn't always provide correct results but the chances of algorithm being wrong are almost negligible.

Note: prime test code is based on this wiki.

Check this out

The 15th Prime number in Fibonacci is

$475420437734698220747368027166749382927701417016557193662268716376935476241$