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

Автор: Сара Чен Сара Чен
Hours обновлено

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

Главный фактор данного любое число – это фактор, который простое число. Факторы при умножении дают другое число. Простое число делится само на себя или на 1.

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

Пример: Простые множители числа 10 — это 2 и 5. Это потому, что 2X5 = 10 и оба 2,5 — простые числа.

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

Чтобы найти простые множители данного числа, мы сначала перебираем все числа от 2 до квадратного корня из числа, а затем проверяем, является ли каждое число простым. Пока исходное число делится на это простое число, мы продолжаем добавлять это простое число на каждой итерации.

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

Каждое простое число больше 40 записывается следующей формулой: n2+н+41. Итак, мы можем заменить n всеми числами, чтобы найти соответствующий простой множитель. например, 02+0+41=41, 12+1+41=43, 22+2+41=47,…

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

  • В этом методе мы будем перебирать числа от 2 до получения квадратного корня из числа, как упоминалось в предыдущем разделе.
  • Для этого нам нужно проверить модуль исходного числа для каждого числа от 2 до квадратного корня из n.
  • Затем мы находим список простых чисел, которые являются делителями n.
  • Это решение имеет временную сложность O(Sqrt(n)).

Алгоритм:

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

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

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

  • Основная концепция этого алгоритма заключается в сохранении наименьшего простого множителя каждого числа до достижения максимального числа.
  • Мы берем наименьшее простое число для каждого данного числа и добавляем его к множеству простых делителей.
  • Наконец, мы делим на это простое число и повторяем эти шаги, пока не достигнем 1.
  • Все это выполняется за временную сложность O(log(n)), что значительно повышает эффективность решения.
  • Что позволяет вычислять простые множители гораздо больших чисел, чем те, с которыми мы могли бы иметь дело, используя предыдущий подход.

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

Второй способ — проверить, можно ли записать число как 6n-1 или 6n+1, поскольку любое простое число, кроме 2 и 3, должно быть записано в одной из двух формул. например, 5=6(1)-1, 19=6(3)+1,… .

Алгоритм:

Определите массив массивов для хранения наименьшего простого множителя каждого числа со значением индекса в качестве начального значения для каждого элемента числа. массив.

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]

СТАТЬИ ПО ТЕМЕ

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

Здесь мы покажем код в Python язык для нахождения простых делителей заданного числа итеративным методом:

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
4

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

В этом разделе показан код в Python язык Используя метод решета, найдите простые множители заданного числа.

import math
High = (int)(1e5+7)
array=[0 for i in range(High)]
# function to generate all the smallest prime 
def Sieve():
#factors of the numbers until the maximum  number
    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):
#We will keep dividing until we reach 1
    if n == 1:
        return
    print((int)(array[n]))
    PrimeFactors((int)(n/array[n]))
#Here we call the function after dividing it by this prime
Sieve()
n=(int)(input("Enter the number you want: "))
PrimeFactors(n)

Вывод:

Enter the number you want: 4
2
2

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

Это то же решение, что и итеративное решение Python, но написанное на Язык C.

Мы просим пользователя ввести число, затем для каждого числа от 2 до квадратного корня из этого числа нам нужно проверить, делится ли оно, распечатав все вхождения этого множителя.

#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 с использованием рекурсии

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

Это то же решение, что и рекурсивное решение Python, но написанное на C.

Мы можем попросить пользователя ввести номер; затем мы создаем массив простых чисел, в котором хранится наименьший простой множитель каждого числа. Наконец, мы вызываем рекурсивную функцию Prime Factors, которая делит заданное число на его наименьший простой множитель и вспоминает себя, пока не достигнет единицы.

#include <stdio.h>
int Max = 100007;
int array[100007];
void Sieve()//helping function to generate all the smallest //prime factors of the numbers until the maximum number
{
    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)//keep dividing until we reach 1
    {
        return;
    }
    printf("%d\n",array[n]);
    PrimeFactors(n/array[n]);//call the function after dividing by //this prime
}
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

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

  • Один из самых интересных фактов заключается в том, что любое четное число, кроме 2, может быть суммой двух простых чисел.
  • Например: 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3… и т. д.
  • Другой факт заключается в том, что не существует последовательных простых чисел, кроме 2 и 3, поскольку единственным четным простым числом является число 2.
  • Также все простые числа, кроме 2 и 3, можно записать в следующем виде: 6 * n + 1 или 6 * n – 1, где n — целое положительное число.
  • Набор простых делителей числа уникален.
  • Число 1 не является ни простым, ни составным.
  • Простая факторизация чисел может помочь решить такие проблемы, как делимость, упрощение дробей и нахождение общего знаменателя различных дробей.
  • Кроме того, одним из интересных применений факторизации простых чисел является взлом секретных кодов, основанных на числах.