40 lines
1.1 KiB
C++
40 lines
1.1 KiB
C++
/*
|
||
* Задание 3
|
||
* Написать программу для факторизации заданного с клавиатуры нечетного
|
||
* числа методом Ферма (указать простые множители и их кратность). Для
|
||
* анализа числа на простоту использовать решето Эратосфена
|
||
*/
|
||
|
||
#include <iostream>
|
||
#include <cmath>
|
||
|
||
bool isPerfectSquare(int num) {
|
||
int s = static_cast<int>(sqrt(num));
|
||
return (s * s == num);
|
||
}
|
||
|
||
int main() {
|
||
long long n;
|
||
std::cout << "Введите n (произведение двух простых чисел p и q): ";
|
||
std::cin >> n;
|
||
|
||
long long m = static_cast<long long>(sqrt(n));
|
||
long long x = 1;
|
||
|
||
while (true) {
|
||
long long q = (m + x) * (m + x) - n;
|
||
if (isPerfectSquare(q)) {
|
||
long long k = static_cast<long long>(sqrt(q));
|
||
long long p = m + x - k;
|
||
long long q_value = m + x + k;
|
||
|
||
std::cout << "Найдены p и q: p = " << p << ", q = " << q_value << std::endl;
|
||
break;
|
||
}
|
||
x++;
|
||
}
|
||
|
||
return 0;
|
||
}
|
||
|