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

Asal çarpanlara ayırma nedir?

Bir sayının asal çarpanı, kendisi de bir çarpan olan bir sayıdır. asal sayıSadece 1'e ve kendisine bölünebilen sayı.

Örnek: 10'un asal çarpanları 2 ve 5'tir, çünkü 2 × 5 = 10.

Yinelemeyi Kullanarak Asal Faktörleri Bulma

2'den √n'ye kadar yineleyin ve bölünebilirliği kontrol edin. n, mevcut aday tarafından bölünebiliyorsa, bölme işlemini yapın ve yazdırın.

Örnek: 40'tan büyük her asal sayı n'ye uyar²+n+41, yani n = 0, 1, 2, 41, 43, 47 sonuçlarını verir.

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

• 2'den √n'ye kadar olan sayıları yineleyin.
• Her bir aday için n'nin mutlak değerini kontrol edin; sıfır kalan, adayın asal çarpan olduğu anlamına gelir.
• n'yi bölen tüm asal sayıları toplayın.
• Bu rutin O(sqrt(n)) zaman karmaşıklığında çalışı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ı

Elek yöntemi, her sayının en küçük asal çarpanını maksimum bir sınıra kadar saklayarak, ön hesaplama sonrasında çarpanlara ayırma maliyetini önemli ölçüde azaltır.

• En yüksek sınıra kadar olan her tamsayının en küçük asal çarpanını kaydedin.
• En küçük asal sayıyı alın ve çarpanlar kümesine ekleyin.
• Sayıyı o asal sayıya bölün ve 1'e ulaşana kadar tekrarlayın.
• Her sorgu yaklaşık O(log n) sürede çalışır.

Örnek: 2 ve 3 dışında bir asal sayı 6n-1 veya 6n+1 biçimine uyar. Örneğin, 5 = 6(1)-1 ve 19 = 6(3)+1.

Algoritma: bir tanımla dizi Her sayının en küçük asal çarpanını, her eleman için başlangıç ​​değeri olarak indeksi kullanarak saklayan bir fonksiyondur.

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]

İlgili Makaleler

• Grafik Veri Yapısı ve Algorithms
• Gezgin Satıcı Sorunu
• Bölme Yöntemi Algoritması
• Kova Sıralama Algoritması

Python Yinelemeyi Kullanan Asal Faktörler

Aşağıdaki Python Bu kod, yinelemeli deneme-bölme yöntemini kullanarak asal çarpanları bulur:

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
2
2

Python Özyinelemeyi Kullanan Asal Faktörler

MKS Python Aşağıdaki kod, verilen bir sayının asal çarpanlarını bulmak için elek yöntemini kullanır.

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)

Çıktı:

Enter the number you want: 4
2
2

Yinelemeyi Kullanan C Prime Factors Programı

Aynı yinelemeli çözüm şu şekilde yazılmıştır: C: Bir sayı girin, ardından 2'den √n'ye kadar her aday için bölünebilirliği kontrol edin ve asal çarpanların her geçtiği yeri yazdırın.

#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ı

Özyinelemeli C sürümü şunu yansıtır: Python Birinci adım: En küçük asal çarpanların dizisini oluşturun, ardından n 1'e ulaşana kadar bu çarpana bölme işlemini yineleyin.

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

Çıktı:

Enter the number you want: 2
2

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

• 2 dışında herhangi bir çift sayı, iki asal sayının toplamı olarak yazılabilir (4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3).
• 2 ve 3 dışında ardışık asal sayı yoktur, çünkü 2 tek çift asal sayıdır.
• 2 ve 3 hariç tüm asal sayılar, n pozitif bir tamsayı olmak üzere, 6n + 1 veya 6n − 1 biçimine uyar.
• Bir sayının asal çarpanlarının kümesi tektir.
• 1 sayısı ne asal ne de bileşik sayıdır.
• Asal çarpanlara ayırma, bölünebilirlik, kesirlerin sadeleştirilmesi ve ortak paydaların bulunmasına yardımcı olur.
• Asal çarpanlara ayırma, sayı tabanlı kriptografik kodların da temelini oluşturur.

SSS