Лучший способ найти все главные факторы огромных целых чисел в C? - PullRequest
Новая
       81

Лучший способ найти все главные факторы огромных целых чисел в C?

0 голосов
/ 20 апреля 2020

Я написал код в C, который в основном составляет список всех главных факторов огромного числа, который хранится с использованием библиотеки gmp. Вот оно: 

int is_div(mpz_t number, mpz_t i) {
    return mpz_divisible_p(number,i)!=0;
}

mpz_t * prime_divs(mpz_t number){
    mpz_t * prime_dividers = NULL;
    mpz_t i, i_squared,TWO, comp;
    mpz_inits(i, i_squared, TWO, comp, NULL);
    mpz_set_ui(i,2);
    mpz_mul(i_squared, i ,TWO);
    while(mpz_cmp(i_squared,number)<=0){
        if(is_div(number,i)){
            mpz_fdiv_q(comp, number, i);
            if(is_prime(i)) append(&prime_dividers,i);
            if(is_prime(comp)) append(&prime_dividers,comp);
        }
        mpz_add_ui(i,i,1);
        mpz_mul(i_squared, i ,i);
    }
    mpz_clears(i, i_squared, TWO, comp, NULL);
    return prime_dividers;
}

Обратите внимание, что функция int is_prime(mpz_t n) здесь не определена, потому что она довольно длинная. Просто знайте, что это реализация детерминированного варианта c (до 3 317 044 064 679 887 385 961 981) теста первичности Миллера-Рабина. То же самое касается функции void append(mpz_t** arr, mpz_t i), это просто функция, которая добавляет его в список.

Так что моя функция prime_divs ищет все целые числа i в диапазоне [2,sqrt(number)], которые разделить number. Если это так, то он вычисляет свой дополнительный делитель (т.е. number/i) и определяет, являются ли какие-либо из них простыми числами. Будут ли эти целые числа простыми, тогда они будут добавлены в список с помощью append.

Есть ли способ сделать prime_divs быстрее?

1 Ответ

1 голос
/ 20 апреля 2020

Я подозреваю, что вы можете сэкономить время, сначала проверив наличие небольших делителей. Используйте Сито Эратосфена, чтобы составить список простых чисел ниже 5000 или 10000. Затем используйте этот список, чтобы найти мелкие факторы, если таковые имеются, вашего большого числа. Каждый раз, когда вы находите множитель (возможно, несколько раз для одного и того же фактора), делите этот множитель, чтобы уменьшить размер целевого числа.

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

Только тогда вы должны вызвать тест МР, чтобы найти остальные факторы.

...