Задача взята с сайта e-olymp.com.
Найти [latex]N[/latex]-е по порядку простое число Фибоначчи.
Во входном файле число [latex]N[/latex], [latex]\left(1\leq N\leq 10 \right)[/latex] В выходной файл следует записать [latex]N[/latex]-е по порядку простое число Фибоначчи.
Тесты
| [latex]N[/latex] | Простое число Фибоначчи |
| 3 | 5 |
| 5 | 89 |
| 7 | 1597 |
| 9 | 514229 |
| 10 | 433494437 |
Код программы
|
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 |
#include <iostream> #include <cmath> using namespace std; int main() { int n; cin >> n; int a, b, c, d, k; a = 1; b = 1; c = 2; bool x; int counter = 0; while (counter < n){ x = true; c = a + b; a = b; b = c; for (int j = 2; j <= sqrt(c) && x; j++) { if((c%j) == 0){ x = false; } } if (x){ counter ++; } } cout << c; return 0; } |
Код на ideone.com
Выполненное задание на сайте e-olimp.com здесь.
Алгоритм решения
- Нам необходимо вычислить первые десять элементов последовательности Фибоначчи. Для этого будем использовать цикл. Пусть [latex] a<b<c [/latex] , где [latex] a, b, c [/latex] являются членами последовательности Фибоначчи. Обозначим, что элемент последовательности равен сумме двух ему предшествующих элементов. Далее присвоим переменным [latex]a, b[/latex] значения следующих элементов последовательности соответственно. Таким образом присваиваем переменной [latex] a [/latex] значение переменной [latex] b [/latex] , переменной [latex] b[/latex] — значение переменной [latex] c [/latex] , а переменной [latex] c [/latex] — значение равное [latex](a+b)[/latex].
- Но не каждый элемент последовательности Фибоначчи является простым числом. Следовательно, нам необходимо проверить делится ли без остатка полученное нами число на какое-либо число, отличное от [latex] 0 [/latex] , [latex] 1 [/latex] и самого себя. Таким образом, если найденный элемент [latex] c [/latex] делится без остатка на целые числа, принадлежащие отрезку [latex]\left[2;\sqrt{c} \right][/latex] , то найденный элемент не является простым числом. Тогда необходимо рассмотреть следующий элемент последовательности Фибоначчи. Для этого введем логическую переменную [latex] (bool x) [/latex] , которая будет принимать значение истинны только тогда, когда число простое.
- Когда логическая переменная принимает значение истины, то увеличим счетчик на единицу. А искать последующие значения элемента[latex] c [/latex] будем до тех пор, пока значение счетчика не станет равным числу [latex] N [/latex].