Bài toán về số Fibonacci và số nguyên tố với Python

51
Lập trình Python

Bài toán. Số Fibonacci và số nguyên tố:

a) Tìm số Fibonacci thứ n (n <= 40)

b) Tìm các số Fibonacci nhỏ hơn hoặc bằng n.

c) Tìm các số Fibonacci nằm trên đoạn [m, n].

d) Tìm các số vừa là số Fibonacci vừa là số nguyên tố trên đoạn [m, n].

Yêu cầu: Nhập vào số n. Trong file đầu ra ghi 4 kết quả như trên. Ví dụ: 

FIBONACCI.INP

FIBONACCI.OUT

3 40

102334155

1 1 2 3 5 8 13 21 34

5 8 13 21 34

5 13

Code tham khảo:

import math
def nguyenTo(n):
    if n < 2: return False
    else:
        m = math.sqrt(n)
        i = 2
        while (n % i) and (i < m):
            i = i + 1
        if i > m: return True
        else: return False
def Fibonacci(n):
    a = 1
    b = 1
    if n == 1:
        return 1
    else:
        for i in range(1, n):
            c = a + b
            a = b
            b = c
        return b
fin = open("FIBONACCI.INP","r")
fout = open("FIBONACCI.OUT","w")
a = fin.readline()
b = a.split()
m, n = int(b[0]), int(b[1])
fout.write(str(Fibonacci(n))+"\n")
for i in range(0,n):
    if Fibonacci(i) < n:
        fout.write(str(Fibonacci(i))+" ")
fout.write("\n")
for i in range(1, n):
    if Fibonacci(i) > m and Fibonacci(i) < n:
        fout.write(str(Fibonacci(i)) + " ")
fout.write("\n")
i = m+1
while Fibonacci(i) < n:
    fi = Fibonacci(i)
    if nguyenTo(fi):
        fout.write(str(fi) + " ")
    i = i + 1
fin.close()
fout.close()