Prime Number checking of Fibonacci sequence Number

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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139

// (c) 2019, Lutfi Shihab #include <iostream> #include <vector> // todo template <typename T> class Matrix { public: Matrix(int rows, int cols) : m_rows(rows), m_cols(cols) {} private: int m_rows; int m_cols; }; /* function that returns nth Fibonacci number */ template <typename T> class Fibonacci { public: Fibonacci(T n) { m_fibNum = fib(n); } operator T() const { return m_fibNum; } operator int() const { return m_fibNum; } friend std::ostream& operator<<(std::ostream& os, Fibonacci<T>& f) { return os << f.m_fibNum; } Fibonacci<T> operator+=(int k) { return m_fibNum += k; } Fibonacci<T> operator %(int k) { return m_fibNum % k; } Fibonacci<T> operator /(int k) { return m_fibNum / k; } bool operator<=(int k) { return m_fibNum < k; } bool operator >(int k) { return m_fibNum > k; } bool operator==(int k) { return m_fibNum == k; } private: void multiply(T F[2][2], T M[2][2]) { T x = F[0][0]*M[0][0] + F[0][1]*M[1][0]; T y = F[0][0]*M[0][1] + F[0][1]*M[1][1]; T z = F[1][0]*M[0][0] + F[1][1]*M[1][0]; T w = F[1][0]*M[0][1] + F[1][1]*M[1][1]; F[0][0] = x; F[0][1] = y; F[1][0] = z; F[1][1] = w; } /* Optimized version of power() */ void power(T F[2][2], T n) { if( n == 0 || n == 1) return; T M[2][2] = {{1,1},{1,0}}; this->power(F, n/2); multiply(F, F); if (n%2 != 0) multiply(F, M); } T fib(T n) { T F[2][2] = {{1,1},{1,0}}; if (n == 0) { return 0; } power(F, n-1); return F[0][0]; } T m_fibNum; }; // Returns n! (the factorial of n) int Factorial(int n) { int result = 1; for (int i = 1; i <= n; i++) { result *= i; } return result; } // Returns true if n is a prime number template<typename T> bool IsPrime(T n) { // Trivial case 1: small numbers if (n <= 1) return false; // Trivial case 2: even numbers if (n % 2 == 0) return n == 2; // Now, we have that n is odd and n >= 3. // Try to divide n by every odd number i, starting from 3 for (T i = 3; ; i += 2) { // We only have to try i up to the squre root of n if (i > n/i) break; // Now, we have i <= n/i < n. // If n is divisible by i, n is not prime. if (n % i == 0) return false; } // n has no integer factor in the range (1, n), and thus is prime. return true; } int main() { for(int i=0; i<300; ++i) { Fibonacci<unsigned long> f(i); if (IsPrime(f)) { std::cout << f << " is a prime number\n"; } } }