Tìm số hạng thứ N của dãy hỗn hợp Fibonacci và số nguyên tố trong C++

Cho dãy: 0, 2, 1, 3, 1, 5, 2, 7, 3... Tìm số hạng thứ N.

Phân tích

Dãy xen kẽ hai dãy con:

• Vị trí lẻ (1-based): dãy Fibonacci (0,1,1,2,3,5,8...).
• Vị trí chẵn: dãy số nguyên tố (2,3,5,7,11...).

Công thức: N lẻ → Fibonacci(N/2); N chẵn → Prime(N/2).

Mã nguồn C++

#include <iostream>
using namespace std;

int findNthPrimeTerm(int n) {
    int primeCount = 0;
    for (int i = 2; ; i++) {
        bool isPrime = true;
        for (int j = 2; j*j <= i; j++) if (i % j == 0) { isPrime = false; break; }
        if (isPrime) primeCount++;
        if (primeCount == n) return i;
    }
    return -1;
}

int FibonacciNthTerm(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) { c = a+b; a=b; b=c; }
    return b;
}

int findNTerm(int N) {
    if (N % 2 == 0) return findNthPrimeTerm(N/2);
    else return FibonacciNthTerm(N/2);
}

int main() {
    cout << "13th term: " << findNTerm(13) << endl; // 8
    cout << "4th term: " << findNTerm(4) << endl;   // 3
    return 0;
}

Đầu ra

13th term of the series is 8
4th term of the series is 3