Υπολογιστής Συνάρτησης Euler (Φι)

Τύπος

How this is calculated

Εισαγάγετε έναν θετικό ακέραιο n (n ≥ 1). Ο υπολογιστής παραγοντοποιεί το n με δοκιμαστική διαίρεση, βρίσκοντας κάθε διακριτό πρώτο p που το διαιρεί. Οι επαναλαμβανόμενοι πρώτοι παράγοντες συμπτύσσονται, οπότε μόνο το σύνολο των διακριτών πρώτων έχει σημασία για τη συνάρτηση.

Ξεκινώντας από φ = n, το αποτέλεσμα πολλαπλασιάζεται με (1 − 1/p) για κάθε διακριτό πρώτο p, που υλοποιείται ως φ = φ − φ/p για την αποφυγή ολίσθησης κινητής υποδιαστολής· η τελική τιμή στρογγυλοποιείται στον πλησιέστερο ακέραιο. Αυτός είναι ο τύπος γινομένου φ(n) = n · Π(1 − 1/p), που ισχύει επειδή η συνάρτηση είναι πολλαπλασιαστική επί πρώτων δυνάμεων που είναι πρώτες μεταξύ τους. Ο λόγος των πρώτων μεταξύ τους φ(n)/n ισούται με αυτό το ίδιο γινόμενο και αναπαριστά την πιθανότητα ένας τυχαίος ακέραιος στο 1..n να είναι πρώτος μεταξύ του με το n.

Ακραίες περιπτώσεις: φ(1) = 1 κατά σύμβαση, και ένα πρώτο n επιστρέφει φ(n) = n − 1 με τον εαυτό του ως μοναδικό πρώτο παράγοντα. Οι είσοδοι πρέπει να είναι ακέραιοι θετικοί αριθμοί· μη ακέραιοι, τιμές κάτω από το 1, ή εξαιρετικά μεγάλα n (πάνω από 10^12) απορρίπτονται. Οι έξοδοι είναι καθαρά πλήθη και δεν έχουν φυσικές μονάδες.