Bài 68. Dãy Fibonacci nguyên tố

Bài 68: Dãy số Fibonacci là dãy số được định nghĩa như sau:
F[1] = 1; F[2] = 1;
F[N] = F[N-1] + F[N-2] với N ≥ 3.
Cho số nguyên dương P (P ≤ 1015). Hãy xác định số lượng số vừa là số nguyên tố, vừa là số Fibonacci và nhỏ hơn hoặc bằng P.
BAI68.INP BAI68.OUT
100 5
Giải thích: từ 0 đến 10 có 5 số vừa là số nguyên tố vừa là số fibonacci: 2, 3, 5, 13, 89.
Thuật toán:
Xây dựng hàm kiểm tra tính nguyên tố của n.
Xây dựng hàm tìm số fibonacci gần nhất nhỏ hơn hoặc bằng n
Chạy vòng lặp từ 2 đến p rồi kiểm tra
Nếu i là số nguyên tố và cũng thuộc dãy fibonacci thì tăng đếm
Đưa đếm ra

Video bài giảng:

Code:

def nguyen_to(u) :
  if u <= 1 :
      return False
  i = 2
  while i * i <= u :
      if u % i == 0 :
          return False
      i += 1
  return True
def fibonacci(a):
  f = list()
  f.append(1)
  f.append(1)
  i = 2
  while f[i-1] < a :
      f.append(f[i - 1] + f[i - 2])
      i += 1
  return f
dem = 0
p = int(input())
for i in range(2,p) :
  if nguyen_to(i) == True and fibonacci(p).count(i) > 0 :
      dem += 1
print(dem)