Finding nth number of primes in Fibonacci sequence (Faster)

Question

I'm taking my first programming course, and my assignment has been to list the nth number of prime numbers in the Fibonacci sequence. So far I've come up with this:

 num = int(input("Enter a number: "))

a = 1
b = 1
c = 0
count = 0
isPrime = True 

while (count < num):
    isPrime = True
    c = a + b

    for i in range(2,c):
        if (c % i == 0):
            isPrime = False
            break

    if (isPrime):
        print (c)
        count = count + 1
    a = b
    b = c

This works, but for any input greater than 10 it takes a really long time, can anyone help me figure out how to make it a bit quicker? I assume it's because a,b and c end up becoming really big, but I'm not sure how to fix this.

Have you taken a look at the docs? They have a really good model. — Zizouz212, Apr 13 '15 at 18:04
possible duplicate of [How to write the Fibonacci Sequence in Python](http://stackoverflow.com/questions/494594/how-to-write-the-fibonacci-sequence-in-python) — Carson Crane, Apr 13 '15 at 18:56
@CarsonCrane Read the question again; that's not what this is asking. — Jeremy, Apr 14 '15 at 00:54

score 1 · Answer 1 · edited May 23 '17 at 10:24

1

fib = lambda n:reduce(lambda x,n:[x[1],x[0]+x[1]], range(n),[0,1])[0]

shortest and fastest fibonacci numbers one liner script in python.

>>> fib(1000)
43466557686937456435688527675040625802564660517371780402481729089536555417949051
89040387984007925516929592259308032263477520968962323987332247116164299644090653
3187938298969649928516003704476137795166849228875L

found here.

edited May 23 '17 at 10:24

Community

1
1

answered Apr 13 '15 at 18:05

Chiyaan Suraj

1,021
2
13
27

of coarse this doesnt find the primes though ... (+1 all the same) – Joran Beasley Apr 13 '15 at 18:19

score 1 · Answer 2 · answered Apr 13 '15 at 19:29

It's easiest to separate generation of fibonacci numbers from testing for primality. Here's a Python implementation of the Miller-Rabin primality test:

def isPrime(n, k=5): # miller-rabin
    from random import randint
    if n < 2: return False
    for p in [2,3,5,7,11,13,17,19,23,29]:
        if n % p == 0: return n == p
    s, d = 0, n-1
    while d % 2 == 0:
        s, d = s+1, d/2
    for i in range(k):
        x = pow(randint(2, n-1), d, n)
        if x == 1 or x == n-1: continue
        for r in range(1, s):
            x = (x * x) % n
            if x == 1: return False
            if x == n-1: break
        else: return False
    return True

Then it is easy to generate fibonacci numbers and test them for primality:

a, b, f = 1, 1, 2
while True:
    if isPrime(f): print f
    a, b, f = b, f, b+f

It won't take too long to find the 22nd prime fibonacci number:

357103560641909860720907774139063454445569926582843306794041997476301071102767570483343563518510007800304195444080518562630900027386498933944619210192856768352683468831754423234217978525765921040747291316681576556861490773135214861782877716560879686368266117365351884926393775431925116896322341130075880287169244980698837941931247516010101631704349963583400361910809925847721300802741705519412306522941202429437928826033885416656967971559902743150263252229456298992263008126719589203430407385228230361628494860172129702271172926469500802342608722006420745586297267929052509059154340968348509580552307148642001438470316229

You can see the program in action at http://ideone.com/L1oQgO. See A005478 or A001605 for more.

score 1 · Answer 3 · answered Apr 13 '15 at 19:54

You definitely should use the following well-known heuristic:

To check if N is a prime number you only need to divide it by the numbers from 2 to sqrt(N).

@user448810 implicitly uses it in the Miller-Rabin primality test. But just in case you just want to improve upon your own code.

score 0 · Answer 4 · answered Apr 27 '15 at 18:32

0

This code does the same as the one line code and is more readable:

def fib(n):
    a=1
    b=1
    for i in range(n-2):
        a,b = b,a+b
    return b

answered Apr 27 '15 at 18:32

nadapez

2,603
2
20
26

Finding nth number of primes in Fibonacci sequence (Faster)

4 Answers4