simplenumbers2

// Якщо остаток від ділення простого числа p на 4 дорівнює 1, то існує таке ціле число m, що m2 + 1 ділиться на p. *****
#include <iostream>
using namespace std;

int simple(int n) { //Функція що перевіряє чи число є простим
	for (int i = 2; i <= n / 2; i++) if ((n % i) == 0) return 0;
	return 1;
}

int main()
{
	int end = 0; //Оголошуєм змінну кінцевого значення
	cout << "Введіть кінцеве значення = ";
	cin >> end; //Введення змінної кінцевого значення
	cout << "Прості числа, що при діленні на 4 дають остачу 1  :" << endl;
	for (int i = 2; i < end; i++) // Цикл, що перебирає від числа 2 до кінцевого, введеного з клавіатури
		if (simple(i) && i % 4 == 1) {	// Виклик функції що перевіряє на простоту числа, Перевірка чи при діленні на 4, остача буде 1
			cout << "P = " << i << endl;
			for (int j = i+1;; j++) {
				if ((j * j + 1) % i == 0) {
					cout << "\tПри M = " << j << " m^2+1 = " << j*j+1 << " ділиться на P" << endl;
					break;
				}
			}
		}
	return 0;
}