Как первичная факторизация гарантирует, что факторы будут первичными? - PullRequest
Новая
       10

Как первичная факторизация гарантирует, что факторы будут первичными?

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

В этом конкретном коде, как он не выдает 6 1, потому что 6 не дает остатка, деля 18 на него. 

int n = 18;
int[] fact = new int[100];
int[] pow = new int[100];
int d = 0; 

for (int i = 2; i <= n; i++) 
{
    int s = 0;

    while(n % i == 0)
    {
        s++; 
        n /= i;
    } 

    if (s > 0)
    {
        fact[d] = i; 
        pow[d] = s;
        d++; 
    }
}

1 Ответ

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

Каждое число является простым или кратным простого. Посмотрите на: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Если оно не делится на простое число, оно не может быть кратно любому кратному этому простому числу либо . Поскольку 18 можно разделить на 2 - 4, 6, 8, 10, и все остальное никогда не нуждается в проверке. Поскольку 19 нельзя разделить на 2, 4, 6, 8 и 10, никогда не нужно проверять. Это 20 делится на 10, никогда не нуждается в проверке. Он уже делится на 2, поэтому мы тогда исключили половину возможных чисел.

Мы делаем это исключение делителей инстинктивно, но обычно только для 2 - тестируем только нечетные числа - но вы можете продвинуться дальше. Так как результат деления также должен быть простым или кратным простому, мы даже можем остановиться, пройдя Квадрат root.

Все, что вам действительно нужно, это непрерывный список простых чисел, идущий вверх к тому, что Prime является> Squar root (PrimeCandidate). Если не считать чтения из памяти, это самый быстрый способ, который я знаю.

Я действительно что-то написал на топи c некоторое время назад, о 5-i sh способах проверки на простое число : https://social.msdn.microsoft.com/Forums/en-US/85fc2406-d2e9-495a-bea7-e516661f8b40/primal-issues-multithreading-lists-in-memory-and-checking-for-prime-number?forum=csharpgeneral

...