Αλγόριθμος πρωταρχικού παράγοντα: C, Python Παράδειγμα

Τι είναι η Prime Factorization;

Ο πρωταρχικός παράγοντας ενός δεδομένου κάθε αριθμός είναι ο παράγοντας που είναι α πρώτος αριθμός. Οι παράγοντες όταν πολλαπλασιάζονται σας δίνουν έναν άλλο αριθμό. Ένας πρώτος αριθμός διαιρείται με τον εαυτό του ή με το 1.

Με άλλα λόγια, οι πρώτοι παράγοντες προσδιορίζονται βρίσκοντας ποιοι πρώτοι αριθμοί πολλαπλασιάζονται μαζί για να σχηματίσουν τον αρχικό αριθμό.

Παράδειγμα: Οι πρώτοι συντελεστές του 10 είναι το 2 και το 5. Αυτό συμβαίνει επειδή το 2Χ5 =10 και τα δύο 2,5 είναι πρώτοι αριθμοί.

Εύρεση των πρωταρχικών παραγόντων με χρήση της επανάληψης

Για να βρούμε τους πρώτους παράγοντες ενός δεδομένου αριθμού, επαναλαμβάνουμε πρώτα όλους τους αριθμούς από το 2 μέχρι την τετραγωνική ρίζα του αριθμού και μετά ελέγχουμε αν κάθε αριθμός είναι πρώτος. Εφόσον ο αρχικός αριθμός διαιρείται με αυτόν τον πρώτο, συνεχίζουμε να προσθέτουμε αυτόν τον πρώτο σε κάθε επανάληψη.

Παράδειγμα:

Κάθε πρώτος αριθμός μεγαλύτερος του 40 γράφεται με τον ακόλουθο τύπο: n²+n+41. Άρα, μπορούμε να αντικαταστήσουμε το n με όλους τους αριθμούς για να βρούμε τον αντίστοιχο πρώτο παράγοντα. πχ 0²+0+41=41, 1²+1+41=43, 2²+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 Prime Factors με χρήση επανάληψης

Είναι η ίδια λύση με την επαναληπτική python αλλά γραμμένη Γ γλώσσα.

Ζητάμε από τον χρήστη να εισαγάγει τον αριθμό και, στη συνέχεια, για κάθε αριθμό από το 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 Prime Factors με χρήση αναδρομής

Αυτή είναι η ίδια λύση με την αναδρομική python αλλά γραμμένη σε C.

Μπορούμε να ζητήσουμε από τον χρήστη να εισάγει τον αριθμό. Στη συνέχεια, κατασκευάζουμε τον πίνακα πρώτων που αποθηκεύει τον μικρότερο πρώτο παράγοντα κάθε αριθμού. Τέλος, ονομάζουμε την αναδρομική συνάρτηση Prime Factors, η οποία διαιρεί τον δεδομένο αριθμό με τον μικρότερο πρώτο παράγοντα του και ανακαλεί τον εαυτό του μέχρι να φτάσει στο ένα.

#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 δεν είναι ούτε πρώτος ούτε σύνθετος.
• Η παραγοντοποίηση των πρώτων αριθμών μπορεί να βοηθήσει στην επίλυση προβλημάτων όπως η διαιρετότητα, η απλοποίηση των κλασμάτων και η εύρεση κοινών παρονομαστών διαφορετικών κλασμάτων.
• Επίσης, μία από τις συναρπαστικές χρήσεις της παραγοντοποίησης πρώτων είναι το σπάσιμο μυστικών κωδικών που βασίζονται σε αριθμούς.