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

Τι είναι η Prime Factorization;

Ο πρώτος παράγοντας ενός αριθμού είναι ένας παράγοντας που ο ίδιος είναι ένας πρώτος αριθμός, διαιρείται μόνο με το 1 και τον εαυτό του.

Παράδειγμα: Οι πρώτοι παράγοντες του 10 είναι το 2 και το 5, αφού 2 × 5 = 10.

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

Επαναλάβετε από το 2 μέχρι το sqrt(n) και ελέγξτε τη διαιρετότητα. Ενώ το n διαιρείται με τον τρέχοντα υποψήφιο, διαιρέστε και εκτυπώστε.

Παράδειγμα: κάθε πρώτος αριθμός μεγαλύτερος από 40 ταιριάζει με n²+n+41, άρα n = 0, 1, 2 αποδίδει 41, 43, 47.

Πώς να εκτυπώσετε έναν πρώτο παράγοντα ενός αριθμού;

• Επαναλάβετε αριθμούς από το 2 έως το sqrt(n).
• Ελέγξτε το μέτρο του 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

Αλγόριθμος κόσκινου

Η μέθοδος Sieve αποθηκεύει τον μικρότερο πρώτο παράγοντα κάθε αριθμού μέχρι ένα μέγιστο όριο, μειώνοντας απότομα το κόστος παραγοντοποίησης μετά τον προ-υπολογισμό.

• Καταγράψτε τον μικρότερο πρώτο παράγοντα κάθε ακέραιου αριθμού μέχρι το μέγιστο όριο.
• Πάρτε αυτόν τον μικρότερο πρώτο αριθμό και προσθέστε τον στο σύνολο των παραγόντων.
• Διαιρέστε τον αριθμό με αυτόν τον πρώτο αριθμό και επαναλάβετε μέχρι να φτάσετε στο 1.
• Κάθε ερώτημα εκτελείται σε περίπου O(log n).

Παράδειγμα: Ένας πρώτος αριθμός εκτός από τους 2 και 3 ταιριάζει στη μορφή 6n-1 ή 6n+1. Για παράδειγμα, 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]

Σχετικά άρθρα

• Δομή δεδομένων γραφήματος και Algorithms
• Πρόβλημα πωλητή ταξιδιού
• Αλγόριθμος μεθόδου διχοτόμησης
• Αλγόριθμος ταξινόμησης κάδου

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

Python Πρωταρχικοί παράγοντες που χρησιμοποιούν την αναδρομή

The Python Ο παρακάτω κώδικας χρησιμοποιεί τη μέθοδο κόσκινου για να βρει τους πρώτους παράγοντες ενός δεδομένου αριθμού.

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)

Παραγωγή:

Enter the number you want: 4
2
2

Πρόγραμμα C Prime Factors με χρήση επανάληψης

Η ίδια επαναληπτική λύση γραμμένη σε C: εισάγετε έναν αριθμό, στη συνέχεια, για κάθε υποψήφιο αριθμό από το 2 έως το sqrt(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;
}

Παραγωγή:

Enter the number you want: 2
2

Πρόγραμμα C Prime Factors με χρήση αναδρομής

Η αναδρομική έκδοση C αντικατοπτρίζει το Python ένα: κατασκευάστε τον πίνακα των μικρότερων πρώτων παραγόντων και, στη συνέχεια, επαναλάβετε τη διαίρεση με αυτόν τον παράγοντα μέχρι το n να φτάσει στο 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;
}

Παραγωγή:

Enter the number you want: 2
2

Μερικά ενδιαφέροντα στοιχεία για τους πρώτους αριθμούς

• Οποιοσδήποτε άρτιος αριθμός εκτός από το 2 μπορεί να γραφτεί ως το άθροισμα δύο πρώτων αριθμών (4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3).
• Δεν υπάρχουν διαδοχικοί πρώτοι αριθμοί εκτός από τους 2 και 3, επειδή το 2 είναι ο μόνος άρτιος πρώτος αριθμός.
• Κάθε πρώτος αριθμός εκτός από τους 2 και 3 ταιριάζει στη μορφή 6n + 1 ή 6n − 1, όπου n είναι ένας θετικός ακέραιος αριθμός.
• Το σύνολο των πρώτων παραγόντων ενός αριθμού είναι μοναδικό.
• Ο αριθμός 1 δεν είναι ούτε πρώτος ούτε σύνθετος.
• Η παραγοντοποίηση σε πρώτους αριθμούς βοηθά στη διαιρετότητα, στην απλοποίηση κλασμάτων και στην εύρεση κοινών παρονομαστών.
• Η παραγοντοποίηση σε πρώτους παράγοντες στηρίζει επίσης τους κρυπτογραφικούς κώδικες που βασίζονται σε αριθμούς.

Συχνές Ερωτήσεις