Алгоритъм за първичен фактор: C, Python Пример
Сара Чен
Какво е просто факторизиране?
Основният множител на дадено който и да е числото е факторът, който е a просто число. Факторите, когато се умножат, ви дават друго число. Простото число се дели на себе си или на 1.
С други думи, простите множители се определят, като се установи кои прости числа се умножават, за да образуват оригиналното число.
Пример: Простите множители на 10 са 2 и 5. Това е така, защото 2X5 =10 и двете 2,5 са прости числа.
Намиране на основните множители с помощта на итерация
За да намерим простите множители на дадено число, първо преминаваме през всички числа от 2 до квадратния корен на числото и след това проверяваме дали всяко число е просто. Докато оригиналното число се дели на това просто число, ние продължаваме да добавяме това просто число с всяка итерация.
Пример:
Всяко просто число, по-голямо от 40, се записва в следната формула: n2+n+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 Програма за прости множители, използваща итерация
Това е същото решение като итеративното 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 Програма за прости множители, използваща рекурсия
Това е същото решение като рекурсивното на 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 не е нито просто, нито съставно.
- Разлагането на числа на прости множители може да помогне за решаването на проблеми като делимост, опростяване на дроби и намиране на общи знаменатели на различни дроби.
- Освен това едно от вълнуващите приложения на разлагането на прости множители е разбиването на тайни кодове, базирани на числа.
