Расчет простых множителей числа

Question

У меня есть следующий запрос:

найти простые множители (без их показателей) для заданного числа n с 2 < n < 999999.

У меня есть the following algorithm, который решает эту проблему, но, кажется, есть некоторые проблемы с производительностью:

bool is_prime(const unsigned long int &number) { 
    for (unsigned long int i = 2; i <= sqrt(number); i++) { 
     if (number%i == 0) return false; 
    } 
    return true; 
} 
unsigned long int next_prime(unsigned long int current) { 
    current++; 
    while (!is_prime(current)) { 
     current++; 
    } 
    return current; 
} 

// THE PROBLEM SOLVER 
vector<unsigned long int> find_divisors(const unsigned long int &n) { 
    vector<unsigned long int> divisors; 
    for (unsigned long int i = 2; i <= n; i = next_prime(i)) { 
     if (n%i == 0) divisors.push_back(i); 
    } 
    return divisors; 
} 

Выпуск: для больших чисел, алгоритм занимает слишком много времени (для максимального допустимого числа, требуется около 1,5 секунды).

Примеры (которые являются правильными):

• n = 1620 выходы {2, 3, 5}
• n = 2048 выходы {2}
• n = 4096 выходы {2}

Answer 1

Ваш предлагаемый алгоритм, как вы подразумеваете, ужасно неэффективен. Но для указанного диапазона это очень простая проблема для компьютеров с 32-разрядной целочисленной арифметикой. Вот как это сделать:

for (int p = 2 ; p * p <= n ; p = (p == 2) ? 3 : (p + 2)) { // p = 2,3,5,7,9,...until p > sqrt(n) 
    if (n % p) continue ; 
    divisors.push_back (p) ;  // p divides n, so save it 
    do n /= p ; while (!(n % p)) ; // Remove all divisors p from n 
} 
if (n > 1) divisors.push_back (n) ; 

Я не собираюсь объяснять: вы узнаете гораздо больше, полагая, что это для себя. Это может быть сделано немного быстрее благодаря различным микрооптимизациям, но это по существу оптимально для вашего заявленного диапазона, если вы не используете простые таблицы. Такие таблицы могут сделать это немного быстрее, но в большинстве случаев это не будет стоить того.

Answer 2

Вы не кэшировать любой из ваших результатов: вместо этого вы должны рассмотреть возможность использования

map<int,vector<int>> vPrimes 

Эта карта будет содержать все простые множители заданного числа. Например, для 50 он будет содержать 2,5 (2 * 5 * 5 = 50). Затем предположим, что вы попытаетесь вычислить его на 300, затем вы проверите (300% 3 = 0), затем добавьте 3 к списку, в результате получив (2,3,5).

Надежда, что помогает,

Answer 3

из википедии:

факторизации больших целых чисел, как полагают, вычислительно очень сложная проблема, и безопасность многих современных криптографических систем основана на ее неосуществимости . [11]

Ваш лучший подход заключается в грубой силе простых факторов с помощью сита Eratosthenes или алгоритма pollard-rho. Поскольку цифры не такие большие (100000 на макс.), Вы могли бы очень быстро прекомпостировать все основные факторы на современном оборудовании. ура

Answer 4

Основная оптимизация: вам не нужно искать до n, вы можете просто выполнить поиск в sqrt (n). Все остальное простое. Вторичная оптимизация: разделите простые числа, которые вы найдете, чтобы уменьшить границу, к которой вы выполняете поиск.

Больше можно было бы сделать, но это уже в тысячу раз быстрее.

vector<unsigned long int> find_divisors(const unsigned long int &m) { 
    unsigned long int n = m; 
    vector<unsigned long int> divisors; 
    if (n%2 == 0) { 
    divisors.push_back(2); 
    while (n%2==0) n/=2; 
    } 

    for (unsigned long int i = 3; i*i <= n; i += 2) { 
     if (n%i) continue; 
     divisors.push_back(i); 
     while (n%i==0) n/=i; 
    } 
    if (n > 1) divisors.push_back(n); 
    return divisors; 
} 

Answer 5

Для такого ограниченного диапазона чисел вполне приемлемо жестко кодировать таблицу простых чисел до 1000.

int P[169]= { 
    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, 1009   
}; 

int i= 0; 
while (i < 169 && P[i] < Number) 
{ 
    if (Number % P[i] != 0) 
     i++; 
    else 
     Number/= P[i]; // P[i] is a factor 
} 
// Number is the last factor