Самый быстрый способ найти основные факторы после сита

Я сохранил все простые числа до диапазона в векторе primes после sieve, Теперь я хочу найти все основные факторы n в течение короткого времени.

Мой код:

    i=0
    while(primes[i]<=n)
    {
        if(n%primes[i]==0)
        {
           cout<<primes[i]<<endl;
        }
        while(n%primes[i]==0)
            n/=primes[i];
        i++;
    }

Но это не эффективно, пожалуйста, предложите любые возможные модификации. Спасибо!

Источник

3 ответа

Я думаю, что это должно быть более эффективным, потому что я исключаю другой цикл в вашем коде. Я проверял это в C#, за исключением того, что я проверял это с жестко закодированным числом.

Я думаю, что это код, который вы хотите увидеть. Надеюсь, это более эффективно. Я написал это на C# и у меня не было списка простых чисел, поэтому я жестко запрограммировал его (или достаточно для моего примера)

Код, я думаю, будет работать на основе вашего кода

i = 0
while(n > 1)
{
    if(n % primes[i] == 0)
    {
       cout<<primes[i]<<endl;
       n /= primes[i];
    }
    else
        i++;
}

Код, который я написал на C#, который, как мне кажется, имитировал ваш код или, по крайней мере, то, что, по вашему мнению, вы делали.

        int n = 1806046;
        int[] primes;
        primes = new int[] { 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, 439, 601, 733, 941, 1151 };
        int i = 0;
        while (n > 1)
        {
            if (n % primes[i] == 0)
            {
                comboBox1.Items.Add(primes[i]);
                n /= primes[i];
            }
            else
                i++;
        }

Это код, который я протестировал и основал его на C#. Который работал отлично и перебрал все числа вместо простых чисел.

        int x = 1806046;
        int i = 2;

        while (x > 1)
        {
            if (x % i++ == 0)
            {
                x /= --i;
            }
        }
Источник

Вы проверяете все простые числа до n, Вам не нужно это делать. После того, как вы удалили все факторы, включая sqrt(n) тогда либо оставшаяся неструктурированная часть сама является простой, либо она равна 1.

Вы можете выйти из внешнего цикла, когда n == 1 поскольку больше нет главных факторов, которые можно найти. Подумайте о числе, как 16, с множеством небольших простых факторов.

Вы входите во внутренний цикл каждый раз через внешний цикл. Вам не нужно делать это; вам нужен только внутренний цикл, когда ваш if правда.

Однажды внутри if Вы можете сохранить повторение расчета модуля, изменив while цикл до do петля.

i = 0;

// Find prime factors up to square root.
limit = sqrt(n);
while ((primes[i] <= limit) && (n > 1))
{
    if (n % primes[i] == 0)
    {
       cout << primes[i] << endl;
       do 
       {
           n /= primes[i];
       } while (n % primes[i] == 0);
    }
    i++;
}

// Find possible factor above square root.
if (n > 1) 
{
    cout << n << endl;
}

Я не проверял код, поэтому лучше проверить его самостоятельно.

Источник

Ключом к решению этой проблемы является понимание, что может быть только одно простое число>= square_root(N) .

Итак, вы можете просто перебрать список простых чисел вплоть до square_root (N). Вы можете сделать что-то вроде этого кода ниже:

Фактор генерации

Источник
Другие вопросы по тегам