Вашу программу можно значительно ускорить. Она у вас работает линейно по n
, а можно её переделать так, что время работы будет пропорционально квадратному корню из n
.
Для этого нужно заметить, что все делители числа n
состоят из тех же простых чисел, что и само число n
.
Если n = (p1^a1)*(p2^a2)*...*(pm^am)
, то каждый из делителей содержит число p1
в степени от 0 до a1
, p2
в степени от 0 до a2
, и так далее.
Всего делителей числа n
ровно (a1+1)(a2+1)...(am+1)
штук.
Алгоритм поиска делителей таков:
Разложить число n
на простые сомножители, эта операция потребует не более sqrt(n)
действий.
Перебрать все сочетания простых делителей с учётом их степеней. Эта операция потребует порядка (a1+1)(a2+1)...(am+1)
действий - пренебрежимо мало по сравнению с квадратным корнем.
Программу сможете написать?
UPDATE
По просьбе топик-стартера прикладываю программу. Я поленился считывать число из stdin
, раскладываемое число захардкожено в main
-е.
Программа печатает разложение 64-х битного числа на простые множители и список делителей. В примере четыре числа:
- 232848, 120 делителей
- 45196767, 60 делителей
- 2097695047, 12 делителей,
- 2147483647, 2 делителя, большое простое число, самое большое простое 31-битное число.
Кроме того, если раскомментировать в main проверку для 18446744073709551557 (максимальное простое 64-х битное число), можно узнать максимально возможное время работы программы на вашем процессоре.
У меня на core-i7 с максимальное оптимизацией работает в худшем случае 11 секунд. Если заменить брут-форс тест простоты на что-нибудь более эффективное, то можно свести время работы вообще к нулю.
232848 == 1 * 2^4 * 3^3 * 7^2 * 11^1
1, 2, 4, 8, 16, 3, 6, 12, 24, 48, 9, 18, 36, 72, 144, 27, 54, 108, 216, 432, 7, 14, 28, 56, 112, 21, 42, 84, 168, 336, 63, 126, 252, 504, 1008, 189, 378, 756, 1512, 3024, 49, 98, 196, 392, 784, 147, 294, 588, 1176, 2352, 441, 882, 1764, 3528, 7056, 1323, 2646, 5292, 10584, 21168, 11, 22, 44, 88, 176, 33, 66, 132, 264, 528, 99, 198, 396, 792, 1584, 297, 594, 1188, 2376, 4752, 77, 154, 308, 616, 1232, 231, 462, 924, 1848, 3696, 693, 1386, 2772, 5544, 11088, 2079, 4158, 8316, 16632, 33264, 539, 1078, 2156, 4312, 8624, 1617, 3234, 6468, 12936, 25872, 4851, 9702, 19404, 38808, 77616, 14553, 29106, 58212, 116424, 232848,
45196767 == 1 * 3^2 * 7^3 * 11^4
1, 3, 9, 7, 21, 63, 49, 147, 441, 343, 1029, 3087, 11, 33, 99, 77, 231, 693, 539, 1617, 4851, 3773, 11319, 33957, 121, 363, 1089, 847, 2541, 7623, 5929, 17787, 53361, 41503, 124509, 373527, 1331, 3993, 11979, 9317, 27951, 83853, 65219, 195657, 586971, 456533, 1369599, 4108797, 14641, 43923, 131769, 102487, 307461, 922383, 717409, 2152227, 6456681, 5021863, 15065589, 45196767,
2097695047 == 1 * 7^3 * 2473^2
1, 7, 49, 343, 2473, 17311, 121177, 848239, 6115729, 42810103, 299670721, 2097695047,
2147483647 == 1 * 2147483647^1
1, 2147483647,
Экстремальный случай:
18446744073709551557 == 1 * 18446744073709551557^1
1, 18446744073709551557,
real 0m11.161s
user 0m11.047s
sys 0m0.031s
#include <stdint.h>
#include <math.h>
#include <vector>
#include <iostream>
using namespace std;
// --------------------------------------------------------------------------------------------------
// Типы
// --------------------------------------------------------------------------------------------------
// Алгоритм работает даже для 64-х битных беззнаковых целых.
// В худшем случае 2^64 - 57 обрабатывает на core i7 за 11 секунд (с включенной оптимизацией).
typedef uint64_t number_t;
// Простой делитель и его степень
class factor_t {
public:
number_t prime;
int degree;
factor_t(number_t prime, int degree) : prime(prime), degree(degree) {}
};
// Разложения числа в произведение простых делителей
typedef vector<factor_t> factorization_t;
// Список делителей числа
typedef vector<number_t> divisor_list_t;
// --------------------------------------------------------------------------------------------------
// Разложение на множители
// --------------------------------------------------------------------------------------------------
// Разложить число на простые делители
factorization_t factorize(number_t n);
// Построить список всех делителей из заданного разложения.
divisor_list_t build(factorization_t factorization);
// --------------------------------------------------------------------------------------------------
// Тестовый пример
// --------------------------------------------------------------------------------------------------
void do_it(number_t n) {
// Разложим число на простые делители
factorization_t factors = factorize(n);
// Напечатаем получившееся разложение
cout << n << " == 1";
for (factorization_t::const_iterator f = factors.begin(); f != factors.end(); f++) {
cout << " * " << (*f).prime << "^" << (*f).degree;
}
cout << endl;
// Составим список делителей
divisor_list_t divisors = build(factors);
// распечатаем список делителей
for (divisor_list_t::const_iterator p_div = divisors.begin(); p_div != divisors.end(); p_div++) {
cout << *p_div << ", ";
}
cout << endl;
}
int main() {
// Много делителей
do_it(232848); // 2**4 * 3**3 * 7**2 * 11
cout << endl;
// Число больше, а делителей меньше
do_it(45196767); // 3**2 * 7**3 * 11**4
cout << endl;
// Пример числа с большим простым делителем
do_it(2097695047); // 7**3 * 2473**2
cout << endl;
// ОЧЕНЬ БОЛЬШОЕ простое число (2^31-1)
do_it(2147483647UL);
cout << endl;
// ГИГАНТСКОЕ простое число (2^64-57)
// do_it(18446744073709551557ULL);
// cout << endl;
}
// --------------------------------------------------------------------------------------------------
// Реализация
// --------------------------------------------------------------------------------------------------
// Для ускорения разложения на множители захардкодим список простых чисел менее 1000
const number_t SMALL_PRIMES[] = {
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73,
79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163,
167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251,
257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443,
449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557,
563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647,
653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757,
761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863,
877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983,
991, 997
};
// Первое простое число, не попавшее в список выше.
const number_t FIRST_NOT_SO_SMALL_PRIME = 1009;
// Вместо того, чтобы извлекать квадратные корни из чисел, будем сравнивать их с
// квадратами простых чисел. Трюк работает для чисел меньших миллиона.
const number_t SMALL_PRIME_SQUARES[] = {
4, 9, 25, 49, 121, 169, 289, 361, 529, 841, 961, 1369, 1681, 1849, 2209, 2809,
3481, 3721, 4489, 5041, 5329, 6241, 6889, 7921, 9409, 10201, 10609, 11449,
11881, 12769, 16129, 17161, 18769, 19321, 22201, 22801, 24649, 26569, 27889,
29929, 32041, 32761, 36481, 37249, 38809, 39601, 44521, 49729, 51529, 52441,
54289, 57121, 58081, 63001, 66049, 69169, 72361, 73441, 76729, 78961, 80089,
85849, 94249, 96721, 97969, 100489, 109561, 113569, 120409, 121801, 124609,
128881, 134689, 139129, 143641, 146689, 151321, 157609, 160801, 167281, 175561,
177241, 185761, 187489, 192721, 196249, 201601, 208849, 212521, 214369, 218089,
229441, 237169, 241081, 249001, 253009, 259081, 271441, 273529, 292681, 299209,
310249, 316969, 323761, 326041, 332929, 344569, 351649, 358801, 361201, 368449,
375769, 380689, 383161, 398161, 410881, 413449, 418609, 426409, 434281, 436921,
452929, 458329, 466489, 477481, 491401, 502681, 516961, 528529, 537289, 546121,
552049, 564001, 573049, 579121, 591361, 597529, 619369, 635209, 654481, 657721,
674041, 677329, 683929, 687241, 703921, 727609, 734449, 737881, 744769, 769129,
776161, 779689, 786769, 822649, 829921, 844561, 863041, 877969, 885481, 896809,
908209, 935089, 942841, 954529, 966289, 982081, 994009
};
const size_t SMALL_PRIMES_NUM = sizeof(SMALL_PRIMES)/sizeof(SMALL_PRIMES[0]);
// Есть ли у числа простой делитель меньше тысячи?
// Для чисел меньших миллиона быстро проверяет простоту.
number_t find_small_divisor(number_t n) {
for (int i = 0; i < SMALL_PRIMES_NUM; i++) {
if (n < SMALL_PRIME_SQUARES[i]) {
// n меньше миллиона и не имеет малых простых делителей.
// Значит n - простое.
return n;
}
number_t rem = n % SMALL_PRIMES[i];
if (rem == 0) {
// Нашли простой делитель
return SMALL_PRIMES[i];
}
}
// Небольшие делители не найдены
return 0;
}
// Найти простой делитель числа
number_t find_prime_divisor(number_t n) {
// сначала ищем маленький делитель
number_t p = find_small_divisor(n);
if (p > 0) {
// нашли!
return p;
}
// Тупо перебираем нечетные числа начиная с первого "не столь маленького" простого числа 1009
// Квадратный корень извлекаем из n+1, чтобы не рисковать ошибкой округления.
number_t lim = number_t(sqrt(n+1));
for (number_t i = FIRST_NOT_SO_SMALL_PRIME; i <= lim; i+=2) {
// Отбрасываем кандидаты, кратные 3-м
// Этого достаточно. Проверка делимости на 5 и 7 не даёт прироста скорости.
if (i%3) {
if (0 == n%i) {
// число i не нужно проверять на простоту. Если бы у него были делители,
// мы бы их нашли на одном и предыдущих шагов.
return i;
}
}
}
// Не нашли. Значит, число простое.
return n;
}
// Найти степень простого числа в разложении на простые множители.
// Внимание! После выполнения функции число n уменьшается: n -> n/p**degree
int prime_degree(number_t& n, number_t prime) {
int degree = 0;
while (0 == n%prime) {
degree ++;
n = n/prime;
}
return degree;
}
// Разложить число на простые делители
factorization_t factorize(number_t n) {
factorization_t result;
while (n>1) {
number_t prime = find_prime_divisor(n);
// После вызова функции n уменьшится
int degree = prime_degree(n, prime);
if (degree > 0) {
result.push_back(factor_t(prime, degree));
}
}
return result;
}
// Служебная функция.
// Пробегает по всем делителям из src и умножает их на все степени простого делителя из factor
divisor_list_t update(const divisor_list_t src, const factor_t factor) {
// Скопируем все делители, не содержащие factor.prime
divisor_list_t result(src);
number_t multiplier = 1;
// В цикле строим все делители, содержащие factor.prime
// Сначала factor.prime в первой степени
// Затем factor.prime в квадрате
// И так далее вплоть до factor.prime в степени factor.degree
for (int i = 1; i <= factor.degree; i++) {
multiplier *= factor.prime;
for (divisor_list_t::const_iterator p_div = src.begin(); p_div != src.end(); p_div++) {
result.push_back((*p_div)*multiplier);
}
}
return result;
}
// Построить список всех делителей из заданного разложения.
divisor_list_t build(factorization_t factorization) {
divisor_list_t result;
// Начинаем список с единицы
result.push_back(1);
for (factorization_t::const_iterator p_factor = factorization.begin();
p_factor != factorization.end();
p_factor ++) {
// По очереди добавляем каждый из простых делителей в уже найденные делители.
result = update(result, *p_factor);
}
return result;
}