Algoritma Faktor Prima : C, Python Example

Apa itu Faktorisasi Prima?

Faktor prima dari suatu hal Apa pun bilangan adalah faktor yaitu a bilangan prima. Faktor bila dikalikan memberi Anda angka lain. Bilangan prima habis dibagi dirinya sendiri atau 1 .

Dengan kata lain, faktor prima ditentukan dengan menemukan bilangan prima mana yang dapat dikalikan bersama untuk membentuk bilangan asli.

ExampleFaktor prima dari 10 adalah 2 dan 5. Ini karena 2X5 = 10 dan 2,5 keduanya merupakan bilangan prima.

Menemukan Faktor Prima menggunakan Iterasi

Untuk menemukan faktor prima dari suatu bilangan tertentu, pertama-tama kita mengulang semua bilangan dari 2 hingga akar kuadrat bilangan tersebut, lalu memeriksa apakah setiap bilangan merupakan bilangan prima. Selama bilangan asli dapat dibagi dengan bilangan prima ini, kita terus menambahkan bilangan prima ini pada setiap pengulangan.

Contoh:

Setiap bilangan prima yang lebih besar dari 40 ditulis dengan rumus berikut: n²+n+41. Jadi, kita dapat mengganti n dengan semua angka untuk menemukan faktor prima yang sesuai. Misalnya, 0²+0+41=41, 1²+1+41=43, 2²+2+41=47,…

Bagaimana cara mencetak faktor prima suatu bilangan?

• Dalam metode ini, kita akan mengulangi angka dari 2 hingga akar kuadrat angka tersebut, seperti yang disebutkan di bagian sebelumnya.
• Untuk itu, kita perlu memeriksa modulus bilangan asli pada setiap bilangan dari 2 hingga akar kuadrat n.
• Kemudian, kita temukan daftar bilangan prima yang merupakan faktor dari n.
• Solusi ini memiliki 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 mengandalkan penyimpanan faktor prima terkecil dari angka-angka, yang mengurangi kerumitan secara signifikan saat menghitung faktor prima untuk angka apa pun. Algoritma Sieve menemukan semua faktor prima dengan cukup efisien.

• Konsep utama dari algoritma ini adalah menyimpan faktor prima terkecil dari setiap bilangan hingga bilangan maksimal.
• Kami mengambil bilangan prima terkecil untuk setiap bilangan tertentu dan menambahkannya ke himpunan faktor prima.
• Terakhir, kita bagi dengan bilangan prima ini dan ulangi langkah ini hingga mencapai 1.
• Ini semua dilakukan dalam kompleksitas waktu O(log(n)), sehingga sangat meningkatkan efisiensi solusi.
• Yang memungkinkan kita menghitung faktor prima dari angka yang jauh lebih besar daripada yang dapat kita tangani menggunakan pendekatan sebelumnya.

Contoh:

Cara kedua adalah memeriksa apakah bilangan tersebut dapat ditulis sebagai 6n-1 atau 6n+1 karena bilangan prima selain 2 dan 3 harus ditulis dalam salah satu dari dua rumus tersebut. misalnya, 5=6(1)-1, 19=6(3)+1,… .

Algoritma:

Mendefinisikan array array untuk menyimpan faktor prima terkecil dari setiap bilangan dengan nilai indeks sebagai nilai awal setiap elemennya susunan.

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 Faktor Prima Menggunakan Iterasi

Di sini, kami akan menunjukkan kode di Python bahasa untuk menemukan faktor prima dari suatu bilangan tertentu dengan metode berulang:

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
4

Python Faktor Prima Menggunakan Rekursi

Bagian ini menunjukkan kode di Python bahasa menggunakan metode saringan untuk mencari faktor prima suatu bilangan tertentu.

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)

Keluaran:

Enter the number you want: 4
2
2

Program Faktor Prima C Menggunakan Iterasi

Ini adalah solusi yang sama dengan solusi python berulang tetapi ditulis Bahasa C..

Kita meminta pengguna untuk memasukkan angkanya, lalu untuk setiap angka dari 2 hingga akar kuadrat dari angka ini, kita perlu memeriksa apakah angka tersebut dapat dibagi dengan mencetak semua kemunculan faktor ini.

#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

Ini adalah solusi yang sama dengan solusi rekursif python tetapi ditulis dalam C.

Kami dapat meminta pengguna untuk memasukkan nomornya; kemudian, kita membuat larik bilangan prima yang menyimpan faktor prima terkecil dari setiap bilangan. Terakhir, kita menyebut fungsi rekursif Faktor Prima, yang membagi bilangan tertentu dengan faktor prima terkecilnya dan mengingat bilangan tersebut hingga mencapai satu.

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

Keluaran:

Enter the number you want: 2
2

Beberapa fakta menarik tentang bilangan prima

• Salah satu fakta yang paling menarik adalah bahwa bilangan genap apa pun selain 2 dapat merupakan jumlahan dari dua bilangan prima.
• Contoh: 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3 … dst.
• Fakta lainnya adalah tidak ada bilangan prima berurutan selain 2 dan 3, karena satu-satunya bilangan prima genap adalah bilangan 2.
• Selain itu, semua bilangan prima kecuali 2 dan 3 dapat ditulis dalam bentuk berikut: 6 * n + 1 atau 6 * n – 1, di mana n adalah bilangan bulat positif.
• Himpunan faktor prima suatu bilangan merupakan himpunan unik.
• Angka 1 bukanlah bilangan prima dan bukan bilangan komposit.
• Faktorisasi prima suatu bilangan dapat membantu memecahkan masalah seperti pembagian, penyederhanaan pecahan, dan mencari penyebut yang sama dari berbagai pecahan.
• Selain itu, salah satu kegunaan menarik dari faktorisasi prima adalah memecahkan kode rahasia yang berbasis bilangan.