Υπολογιστής Ανάλυσης σε Πρώτους Παράγοντες

Τύπος

How this is calculated

Η μόνη είσοδος είναι ένας ακέραιος n που πρέπει να είναι 2 ή μεγαλύτερος· τα δεκαδικά και οι τιμές κάτω από το 2 απορρίπτονται επειδή η ανάλυση σε πρώτους παράγοντες ορίζεται μόνο για ακέραιους μεγαλύτερους από 1. Ο υπολογιστής στρογγυλοποιεί προς τα κάτω την εισαγόμενη τιμή και ελέγχει ότι ισούται με την αρχική είσοδο.

Η παραγοντοποίηση χρησιμοποιεί δοκιμαστική διαίρεση. Διαιρεί πρώτα κάθε παράγοντα του 2, στη συνέχεια δοκιμάζει διαδοχικούς περιττούς διαιρέτες d = 3, 5, 7, ... ενώ το d στο τετράγωνο είναι μικρότερο ή ίσο με το τρέχον πηλίκο. Κάθε φορά που το d διαιρεί ακριβώς, καταγράφεται και το πηλίκο μειώνεται. Μόλις δεν απομένει διαιρέτης έως την τετραγωνική ρίζα, οποιοδήποτε πηλίκο ακόμη μεγαλύτερο από 1 πρέπει να είναι το ίδιο πρώτος και προστίθεται ως ο τελικός παράγοντας. Αυτό είναι αποδοτικό επειδή ένας σύνθετος αριθμός έχει πάντα έναν πρώτο παράγοντα όχι μεγαλύτερο από την τετραγωνική του ρίζα.

Οι ίδιοι πρώτοι ομαδοποιούνται σε ζεύγη βάση^εκθέτης για να παραχθεί η συμβολοσειρά ανάλυσης (για παράδειγμα 360 = 2^3 x 3^2 x 5). Σύμφωνα με το Θεμελιώδες Θεώρημα της Αριθμητικής αυτή η ανάλυση είναι μοναδική μέχρι τη σειρά. Το ραβδόγραμμα δείχνει κάθε διακριτό πρώτο με μια ράβδο μεγέθους ανάλογου του εκθέτη του (πολλαπλότητα). Πολύ μεγάλες είσοδοι πάνω από 10^15 δεν παραγοντοποιούνται για να παραμείνουν τα αποτελέσματα γρήγορα και ακριβή εντός των ορίων κινητής υποδιαστολής.