Факторизация действительно больших чисел
Я бы хотел, чтобы пользователь мог печатать гигантские числа, например: 7777777777777777777777777772
Это 93-разрядное число, а не такое гигантскоеТаким образом, можно было бы упростить грубое форсирование этого.C действительно определяет 64-битные типы, но помимо этого вы сами по себе.
Эта скромная факторизация, которую я бы оценил, может занять несколько минут.
https://www.dcode.fr/prime-factors-decomposition сообщаетответ за секунды.
Конечно, много улучшения могут быть достигнуты.
unsigned __int128 factor(unsigned __int128 x) {
if (x <= 3) {
return x;
}
if (x %2 == 0) return 2;
for (unsigned __int128 i = 3; i <= x/i; i += 2) {
static unsigned long n = 0;
if (++n >= 100000000) {
n = 0;
printf(" %llu approx %.0f\n", (unsigned long long) i, (double)(x/i));
fflush(stdout);
}
if (x%i == 0) {
return i;
}
}
return x;
}
void factors(unsigned __int128 x) {
do {
unsigned __int128 f = factor(x);
printf("%llu approx %.0f\n", (unsigned long long) f, (double)x);
fflush(stdout);
x /= f;
} while (x > 1);
}
void factors(unsigned __int128 x) {
do {
unsigned __int128 f = factor(x);
printf("approx %0.f approx %.0f\n", (double) f, (double)x);
fflush(stdout);
x /= f;
} while (x > 1);
}
Вывод
approx 2 approx 7777777777777778308713283584
approx 2 approx 3888888888888889154356641792
approx 487 approx 1944444444444444577178320896
approx 2687 approx 3992699064567647864619008
99996829 approx 14859790387308
199996829 approx 7429777390798
299996829 approx 4953158749339
399996829 approx 3714859245385
499996829 approx 2971882684351
...
38399996829 approx 38696146902
38499996829 approx 38595637421
approx 1485931918335559335936 approx 1485931918335559335936
Хотя правильный ответиспользовать более эффективные алгоритмы и , а затем учитывать необходимые типы.