Написал алгоритм который разложить число на простые множители, работает хорошо, но медленно. Не засчитывает 2 теста, исчерпан лимит времени. Входное число, которое нужно разложить в пределах от 1 до 2 (на 31 степени) -1. Учёл ввод простого числа, так что это не должно мешать, да и не в нём дело, те 2 теста, которые не проходят по времени не предоставляют простое число, проверял выводом n-1 для любого случая. Как можно ускорить это ?
#include <iostream>
#include <cmath>
using namespace std;
int rozout(long long n);
bool prime(long long n);
int main() {
long long n;
cin >> n;
if (prime(n))
{
cout << n;
return 0;
}
rozout(n);
}
int rozout(long long n)
{
long long i = 2;
while (n > 1)
{
while (n % i == 0)
{
cout << i;
if (n != i) cout << "*";
n /= i;
}
if (i <= 2) i++;
else i += 2;
}
return 1;
}
bool prime(long long n)
{
long double S = sqrt(n);
for (long long i = 2; i <= S; i++)
{
if (n % i == 0)
{
return false;
break;
}
}
return true;
}