Algoritma Faktor Prima : C, Python Example

Apa itu Faktorisasi Prima?

Faktor prima dari suatu bilangan adalah faktor yang merupakan bilangan itu sendiri. bilangan prima, hanya dapat dibagi oleh 1 dan dirinya sendiri.

Contoh: Faktor prima dari 10 adalah 2 dan 5, karena 2 × 5 = 10.

Menemukan Faktor Prima menggunakan Iterasi

Lakukan iterasi dari 2 hingga akar kuadrat n dan periksa keterdivisiannya. Selama n habis dibagi oleh kandidat saat ini, bagi dan cetak hasilnya.

Contoh: setiap bilangan prima yang lebih besar dari 40 cocok dengan n²+n+41, jadi n = 0, 1, 2 menghasilkan 41, 43, 47.

Bagaimana cara mencetak faktor prima suatu bilangan?

• Ulangi angka dari 2 sampai akar kuadrat(n).
• Periksa modulus n terhadap setiap kandidat; sisa nol berarti kandidat tersebut adalah faktor prima.
• Kumpulkan semua bilangan prima yang membagi n.
• Rutinitas ini berjalan dengan kompleksitas waktu O(sqrt(n)).

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

Algoritma Saringan

Metode Sieve menyimpan faktor prima terkecil dari setiap bilangan hingga batas maksimum, sehingga secara signifikan mengurangi biaya faktorisasi setelah pra-komputasi.

• Catat faktor prima terkecil dari setiap bilangan bulat hingga batas maksimum.
• Ambil bilangan prima terkecil itu dan tambahkan ke himpunan faktor.
• Bagilah angka tersebut dengan bilangan prima itu dan ulangi hingga mencapai 1.
• Setiap kueri berjalan dalam waktu sekitar O(log n).

Contoh: Bilangan prima selain 2 dan 3 memiliki bentuk 6n-1 atau 6n+1. Misalnya, 5 = 6(1)-1 dan 19 = 6(3)+1.

Algoritma: mendefinisikan sebuah susunan yang menyimpan faktor prima terkecil dari setiap angka, menggunakan indeks sebagai nilai awal untuk setiap elemen.

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]

Artikel terkait

• Struktur Data Grafik dan Algorithms
• Traveling Salesman Problem
• Algoritma Metode Bagi Dua
• Algoritma Pengurutan Keranjang

Python Faktor Prima Menggunakan Iterasi

Berikut ini Python Kode ini menemukan faktor prima menggunakan metode pembagian-coba iteratif:

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)

Keluaran:

Enter the number you want: 4
2
2

Python Faktor Prima Menggunakan Rekursi

The Python Kode di bawah ini menggunakan metode saringan untuk menemukan faktor prima dari suatu bilangan.

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)

Keluaran:

Enter the number you want: 4
2
2

Program Faktor Prima C Menggunakan Iterasi

Solusi iteratif yang sama ditulis dalam CMasukkan sebuah angka, lalu untuk setiap kandidat dari 2 hingga akar kuadrat n, periksa keterdivisiannya dan cetak setiap kemunculan faktor prima.

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

Keluaran:

Enter the number you want: 2
2

Program Faktor Prima C Menggunakan Rekursi

Versi C rekursif mencerminkan Python Satu: buatlah susunan faktor prima terkecil, lalu lakukan pembagian secara rekursif dengan faktor tersebut hingga n mencapai 1.

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

Keluaran:

Enter the number you want: 2
2

Beberapa fakta menarik tentang bilangan prima

• Setiap bilangan genap selain 2 dapat ditulis sebagai jumlah dari dua bilangan prima (4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3).
• Tidak ada bilangan prima berurutan selain 2 dan 3, karena 2 adalah satu-satunya bilangan prima genap.
• Setiap bilangan prima kecuali 2 dan 3 sesuai dengan bentuk 6n + 1 atau 6n − 1, di mana n adalah bilangan bulat positif.
• Himpunan faktor prima dari suatu bilangan bersifat unik.
• Angka 1 bukanlah bilangan prima maupun bilangan komposit.
• Faktorisasi prima membantu dalam pembagian, penyederhanaan pecahan, dan menemukan penyebut umum.
• Faktorisasi prima juga mendasari kode kriptografi berbasis angka.

Pertanyaan Umum Demo Slot