Asal Faktör Algoritması: C, Python Örnek E-posta

Asal çarpanlara ayırma nedir?

Belirli bir şeyin asal faktörü herhangi sayı bir faktördür asal sayı. Çarpıldığında faktörler size başka bir sayı verir. Asal sayı kendisine veya 1'e bölünebilir.

Başka bir deyişle asal çarpanlar, hangi asal sayıların çarpılarak asıl sayıyı oluşturacağı bulunarak belirlenir.

Örnek E-posta: 10'un asal çarpanları 2 ve 5'tir. Bunun nedeni 2X5 =10 ve 2,5'un her ikisinin de asal sayı olmasıdır.

Yinelemeyi Kullanarak Asal Faktörleri Bulma

Belirli bir sayının asal çarpanlarını bulmak için önce 2'den sayının kareköküne kadar tüm sayıları yineleriz ve ardından her sayının asal olup olmadığını kontrol ederiz. Orijinal sayı bu asal sayıya bölünebildiği sürece, her yinelemede bu asal sayıyı eklemeye devam ederiz.

Örnek:

40'tan büyük her asal sayı aşağıdaki formülle yazılır: n²+n+41. Dolayısıyla karşılık gelen asal çarpanı bulmak için n'yi tüm sayılarla değiştirebiliriz. örneğin, 0²+0+41=41, 1²+1+41=43, 2²+2+41=47,…

Bir sayının asal çarpanı nasıl yazdırılır?

• Bu yöntemde önceki bölümde de belirtildiği gibi 2'den sayının kareköküne kadar olan sayılar üzerinde yineleme yapacağız.
• Bunun için 2'den n'nin kareköküne kadar her sayının orijinal sayının modülünü kontrol etmemiz gerekiyor.
• Daha sonra n'nin çarpanları olan asal sayıların listesini buluruz.
• Bu çözüm O(Sqrt(n)) zaman karmaşıklığındadır.

Algoritma:

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

Elek Algoritması

Eleme yöntemi sayıların en küçük asal çarpanını depolamaya dayanır, bu da herhangi bir sayının asal çarpanlarını hesaplarken karmaşıklığı belirgin şekilde azaltır. Eleme algoritması tüm asal çarpanları bir nebze verimli bir şekilde bulur.

• Bu algoritmanın ana konsepti, her sayının en küçük asal çarpanını maksimum sayıya kadar saklamaktır.
• Verilen her sayı için en küçük asal sayıyı alıp asal çarpanlar kümesine ekliyoruz.
• Son olarak bu asal sayıya bölüyoruz ve 1’e ulaşana kadar bu adımları tekrarlıyoruz.
• Tüm bunlar O(log(n)) zaman karmaşıklığında yapılır ve çözümün verimliliği önemli ölçüde artar.
• Bu da önceki yaklaşımı kullanarak çözebileceğimiz sayılardan çok daha büyük sayıların asal çarpanlarını hesaplamayı mümkün kılıyor.

Örnek:

İkinci yol ise sayının 6n-1 veya 6n+1 olarak yazılabileceğini kontrol etmektir çünkü 2 ve 3 dışında herhangi bir asal sayının iki formülden birinde yazılması gerekir. örneğin, 5=6(1)-1, 19=6(3)+1,… .

Algoritma:

Her sayının en küçük asal faktörünü, dizinin her elemanı için başlangıç ​​değeri olarak indeks değeriyle birlikte saklayacak bir dizi dizisi tanımlayın. dizi.

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 Yinelemeyi Kullanan Asal Faktörler

Burada, bir kod göstereceğiz Python Belirli bir sayının asal çarpanlarını yinelemeli bir yöntemle bulmak için kullanılan dil:

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)

Çıktı:

Enter the number you want: 4
4

Python Özyinelemeyi Kullanan Asal Faktörler

Bu bölümde bir kod gösterilmektedir Python dil Belirli bir sayının asal çarpanlarını bulmak için eleme yöntemini kullanın.

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)

Çıktı:

Enter the number you want: 4
2
2

Yinelemeyi Kullanan C Prime Factors Programı

Yinelemeli python ile aynı çözümdür ancak C dili.

Kullanıcıdan sayıyı girmesini istiyoruz, ardından 2'den bu sayının kareköküne kadar her sayı için, bu faktörün tüm oluşumlarını yazdırarak bölünebilir olup olmadığını kontrol etmemiz gerekiyor.

#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;
}

Çıktı:

Enter the number you want: 2
2

Özyinelemeyi Kullanan C Asal Faktörler Programı

Bu, python özyinelemeli çözümüyle aynı çözümdür ancak C ile yazılmıştır.

Kullanıcıdan numarayı girmesini isteyebiliriz; daha sonra her sayının en küçük asal çarpanını saklayan asal sayılar dizisini oluşturuyoruz. Son olarak verilen sayıyı en küçük asal çarpanına bölen ve bire ulaşana kadar kendini çağıran Asal Çarpanlar özyinelemeli fonksiyon adını veriyoruz.

#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;
}

Çıktı:

Enter the number you want: 2
2

Asal sayılar hakkında bazı ilginç gerçekler

• En ilginç gerçeklerden biri, 2 dışındaki herhangi bir çift sayının, iki asal sayının toplamı olabilmesidir.
• Örneğin: 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3… vb.
• Diğer bir gerçek ise, 2 ve 3 dışında ardışık asal sayıların olmamasıdır, çünkü tek çift asal sayı 2'dir.
• Ayrıca 2 ve 3 hariç tüm asal sayılar şu biçimde yazılabilir: 6 * n + 1 veya 6 * n – 1, burada n pozitif bir tam sayıdır.
• Bir sayının asal çarpanları kümesi benzersizdir.
• 1 sayısı ne asal ne de bileşiktir.
• Sayıların asal çarpanlarına ayrılması, bölünebilme, kesirleri basitleştirme ve farklı kesirlerin ortak paydalarını bulma gibi sorunların çözülmesine yardımcı olabilir.
• Ayrıca asal çarpanlara ayırmanın heyecan verici kullanımlarından biri de sayıya dayalı gizli kodları kırmaktır.