Алгоритм простих множників: C, Python Приклад

Що таке розкладання на прості множники?

Простий множник даного будь-який число - це фактор, який є a просте число. Перемножені множники дають інше число. Просте число ділиться на себе або на 1.

Іншими словами, прості множники визначаються шляхом визначення того, які прості числа множаться разом, щоб утворити вихідне число.

Приклад: Прості множники числа 10 дорівнюють 2 і 5. Це тому, що 2X5 =10 і обидва 2,5 є простими числами.

Знаходження простих множників за допомогою ітерації

Щоб знайти прості множники даного числа, ми спочатку перебираємо всі числа від 2 до квадратного кореня з числа, а потім перевіряємо, чи кожне число є простим. Поки вихідне число ділиться на це просте число, ми продовжуємо додавати це просте число з кожною ітерацією.

приклад:

Кожне просте число, більше 40, записується у такій формулі: n²+n+41. Отже, ми можемо замінити n на всі числа, щоб знайти відповідний простий множник. наприклад, 0²+0+41=41, 1²+1+41=43, 2²+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 Програма простих множників з використанням ітерації

Це те саме рішення, що й ітераційне рішення Python, але написане в ньому Мова С.

Ми просимо користувача ввести число, а потім для кожного числа від 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 Програма простих множників з використанням рекурсії

Це те саме рішення, що й рекурсивне рішення Python, але написане мовою C.

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

#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 не є ні простим, ні складеним.
• Розкладання чисел на прості множники може допомогти вирішити такі проблеми, як подільність, спрощення дробів і знаходження спільних знаменників різних дробів.
• Крім того, одним із захоплюючих застосувань розкладання на прості множники є злам секретних кодів, заснованих на числах.