Алгоритм простых коэффициентов: C, Python Пример

Что такое простая факторизация?

The prime factor of a number is a factor that is itself a простое число, divisible only by 1 and itself.

Пример: prime factors of 10 are 2 and 5, since 2 × 5 = 10.

Нахождение простых множителей с помощью итерации

Iterate from 2 up to sqrt(n) and check divisibility. While n is divisible by the current candidate, divide and print.

Пример: every prime greater than 40 fits n²+n+41, so n = 0, 1, 2 yields 41, 43, 47.

Как напечатать простой делитель числа?

• Iterate numbers from 2 up to sqrt(n).
• Check the modulus of n against each candidate; a zero remainder means the candidate is a prime factor.
• Collect every prime that divides n.
• The routine runs in O(sqrt(n)) time complexity.

Алгоритм:

Set a counter i to 2
While i <= sqrt(n):
    While n % i == 0:
        n = n / i
        print i
    i = i + 1
if n > 1:
    print n

Алгоритм сита

The Sieve method stores the smallest prime factor of every number up to a maximum bound, sharply cutting factorization cost after precomputation.

• Record the smallest prime factor of every integer up to the max limit.
• Take that smallest prime and add it to the factor set.
• Divide the number by that prime and repeat until it reaches 1.
• Each query runs in about O(log n).

Пример: a prime other than 2 and 3 fits the form 6n-1 or 6n+1. For example, 5 = 6(1)-1 and 19 = 6(3)+1.

Алгоритм: определить массив that stores the smallest prime factor of each number, using the index as the initial value for every element.

Set array[1] to 1
Set i to 2
While i*i <= max_number:
    If array[i] == i:
        Set j to i*i
        While j <= max_number:
            If array[j] == j:
                array[j] = i
            j = j + i
    i = i + 1
while the_number != 1:
    print array[the_number]
    the_number = the_number / array[the_number]

Статьи по теме

• Структура данных графа и Algorithms
• Задача коммивояжера
• Алгоритм метода деления пополам
• Алгоритм сортировки ведра

Python Основные множители с использованием итерации

Следующие Python code finds prime factors using the iterative trial-division method:

import math
def PrimeFactors(n):
    for i in range(2, int(math.sqrt(n)) + 1, 1):
        while n % i == 0:  # find all the occurrences of a prime factor
            print((int)(i))
            n = n // i
    if n != 1:  # if the number was originally a prime
        print((int)(n))
n = (int)(input("Enter the number you want: "))
PrimeFactors(n)

Выход:

Enter the number you want: 4
2
2

Python Простые множители с использованием рекурсии

Python code below uses the sieve method to find the prime factors of a given number.

import math
High = (int)(1e5 + 7)
array = [0 for i in range(High)]

# generate smallest prime factors
def Sieve():
    for i in range(1, High):
        array[i] = i
    for i in range(2, math.ceil(math.sqrt(High))):
        if array[i] == i:
            for j in range(i * i, High, i):
                if array[j] == j:
                    array[j] = i

def PrimeFactors(n):  # divide until we reach 1
    if n == 1:
        return
    print((int)(array[n]))
    PrimeFactors((int)(n / array[n]))

Sieve()
n = (int)(input("Enter the number you want: "))
PrimeFactors(n)

Выход:

Enter the number you want: 4
2
2

Программа C Prime Factors с использованием итерации

The same iterative solution written in C: enter a number, then for each candidate from 2 up to sqrt(n), check divisibility and print every occurrence of a prime factor.

#include <stdio.h>
int main()
{
    int n;
    printf("Enter the number you want: ");
    scanf("%d", &n);
    for (int i = 2; i * i <= n; i++)
    {
        while (n % i == 0)  // find all the occurrences of a prime factor
        {
            printf("%d\n", i);
            n /= i;
        }
    }
    if (n != 1)  // if the number was originally a prime
    {
        printf("%d", n);
    }
    return 0;
}

Выход:

Enter the number you want: 2
2

Программа C Prime Factors с использованием рекурсии

The recursive C version mirrors the Python one: build the array of smallest prime factors, then recurse dividing by that factor until n reaches 1.

#include <stdio.h>
int Max = 100007;
int array[100007];

void Sieve()  // smallest prime factors up to Max
{
    for (int i = 1; i < Max; i++)
        array[i] = i;
    for (int i = 2; i * i <= Max; i++)
    {
        if (array[i] == i)
        {
            for (int j = i * i; j < Max; j += i)
            {
                if (array[j] == j)
                    array[j] = i;
            }
        }
    }
}

void PrimeFactors(int n)
{
    if (n == 1)  // divide until we reach 1
        return;
    printf("%d\n", array[n]);
    PrimeFactors(n / array[n]);
}

int main()
{
    Sieve();
    int n;
    printf("Enter the number you want: ");
    scanf("%d", &n);
    PrimeFactors(n);
    return 0;
}

Выход:

Enter the number you want: 2
2

Несколько интересных фактов о простых числах

• Any even number other than 2 can be written as the sum of two primes (4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3).
• There are no consecutive primes other than 2 and 3, because 2 is the only even prime.
• Every prime except 2 and 3 fits the form 6n + 1 or 6n − 1, where n is a positive integer.
• The set of prime factors of a number is unique.
• The number 1 is neither prime nor composite.
• Prime factorization helps with divisibility, fraction simplification, and finding common denominators.
• Prime factorization also underpins number-based cryptographic codes.

Часто задаваемые вопросы (FAQ)