Συνάρτηση φύλλου για πρώτους αριθμούς

primeΗ παρακάτω συνάρτηση φύλλου επιστρέφει TRUE αν ο αριθμός είναι πρώτος και FALSE αν είναι σύνθετος:

=SUMPRODUCT(-(A1/ROW(INDIRECT("1:"&INT(SQRT(A1))))=INT(A1/ROW(INDIRECT("1:"&INT(SQRT(A1)))))))=-1

Η συνάρτηση φτιάχτηκε με βάση τον κλασικό αλγόριθμο, όπου δοκιμάζουμε όλους τους ακέραιους από το 1 την τετραγωνική ρίζα του αριθμού για να βρούμε τους πιθανούς διαιρέτες του αριθμού. Ας δούμε αναλυτικά με ένα παράδειγμα πως δουλεύει. Έστω ότι στο κελί Α1 είναι ο σύνθετος αριθμός 27. Τότε το τμήμα του τύπου (*)

ROW(INDIRECT("1:"&INT(SQRT(A1))))

επιστρέφει τον πίνακα

 
{1\2\3\4\5}

δηλαδή όλους τους ακέραιους από τον 1 έως το ακέραιο μέρος(INT) της τετραγωνικής ρίζας(SQRT) του 27.
Στη συνέχεια διαιρούμε τον 27 με τον πίνακα αυτό:

A1/ROW(INDIRECT("1:"&INT(SQRT(A1))))

και παίρνουμε τις τιμές:

{27\13,5\9\6,75\5,4}

Παρατηρήστε ότι στις τιμές αυτές υπάρχουν 2 ακέραια πηλίκα (27 και 9).
Το τμήμα του τύπου:

INT(A1/ROW(INDIRECT("1:"&INT(SQRT(A1)))))

επιστρέφει τις ακέραιες τιμές της προηγούμενης διαίρεσης

{27\13\9\6\5}

και αν συγκρίνουμε (με το =) τους δύο αυτούς πίνακες:

A1/ROW(INDIRECT("1:"&INT(SQRT(A1))))=INT(A1/ROW(INDIRECT("1:"&INT(SQRT(A1)))))
δηλαδή:
{27\13,5\9\6,75\5,4} ={27\13\9\6\5}

η σύγκριση θα επιστρέψει TRUE μόνο για τις τιμές 27 και 9:

{TRUE\FALSE\TRUE\FALSE\FALSE}

Τις λογικές αυτές τιμές, μετατρέπουμε σε αριθμητικές (**) πολλαπλασιάζοντας με το -1

-(A1/ROW(INDIRECT("1:"&INT(SQRT(A1))))=INT(A1/ROW(INDIRECT("1:"&INT(SQRT(A1))))))

και η σύγκριση γίνετε αριθμητική:

{-1\O\-1\O\O}

Στη συνέχεια, αθροίζω (***) με την SUMPRODUCT τις τιμές αυτού του πίνακα και έχω αποτέλεσμα -2. Όλοι οι σύνθετοι αριθμοί θα δώσουν όπως είναι φυσικό άθροισμα μεγαλύτερο (απολύτως) ή ίσο με 2, ενώ οι πρώτοι, επειδή μοναδικό διαιρέτη στο σύνολο διαιρετών που εξετάζουμε, έχουν τον αριθμό 1, θα δώσουν άθροισμα -1.
Αν τέλος εξισώσουμε το SUMPRODUCT άθροισμα με το -1 θα έχουμε τον τελικό τύπο που θα επιστρέφει TRUE μόνο για πρώτους αριθμούς.

 =SUMPRODUCT(-(A1/ROW(INDIRECT("1:"&INT(SQRT(A1))))=INT(A1/ROW(INDIRECT("1:"&INT(SQRT(A1)))))))=-1

Για τη συνάρτηση αυτή, προσέξτε:
Α) αποτυγχάνει στον αριθμό 1 (τον θεωρεί πρώτο, επιστρέφει TRUE). Για να καλύψετε και την περίπτωση Α1=1, γράψτε τον τύπο έτσι:

 =IF(A1=1;FALSE;SUMPRODUCT(-(A1/ROW(INDIRECT("1:"&INT(SQRT(A1))))=INT(A1/ROW(INDIRECT("1:"&INT(SQRT(A1)))))))=-1)

Β) αν θέλετε να χειριστείτε και αρνητικούς αριθμούς (φυσικά ακέραιους) αντικαταστήστε στους παραπάνω τύπους το όρισμα Α1 με ABS(A1) και ο τύπος γίνεται:

 =IF(ABS(A1)=1;FALSE;SUMPRODUCT(-(ABS(A1)/ROW(INDIRECT("1:"&INT(SQRT(ABS(A1)))))=INT(ABS(A1)/ROW(INDIRECT("1:"&INT(SQRT(ABS(A1))))))))=-1)

Γ) για να σχηματιστεί ο πίνακας των ακεραίων από το 1 έως το ακέραιο μέρος της ρίζας του αριθμού: INT(SQRT(A1)), χρησιμοποιείται η συνάρτηση ROW, η οποία, τον μεγαλύτερο αριθμό που μπορεί να επιστρέψει είναι ο 1048576=2^20, δηλαδή το μέγιστο πλήθος γραμμών του φύλλου (για excel 2007 και νεότερο).  Άρα, επειδή το τετράγωνο του 2^20 είναι ο αριθμός 1.099.511.627.776, εκεί κάπου τελειώνουν και οι δυνατότητες της συνάρτησης. Για την ακρίβεια ο πιο μεγάλος αριθμός για τον οποίο μπορεί να αποφανθεί η συνάρτηση είναι ο 1.099.513.724.928 και ο πιο μεγάλος πρώτος ο 1.099.513.724.891. Θα έλεγα πολύ καλά, αν θυμηθούμε ότι το excel δεν χειρίζεται αριθμούς με περισσότερα από 15 ψηφία. Για το excel 2003 και παλαιότερα, η συνάρτηση φυσικά και δουλεύει, άλλα έχει πολύ μικρότερες δυνατότητες.

Δ) Όπως παρατηρήσατε, η συνάρτηση κάνει πολλούς εσωτερικούς υπολογισμούς και ως εκ τούτου είναι “βαριά”. Μην το παρακάνετε με δεκάδες χιλιάδες εγγραφές της συνάρτησης στο ίδιο φύλλο.

Στην εικόνα βλέπετε ένα τμήμα φύλλου όπου ο παραπάνω τύπος έχει χρησιμοποιηθεί σε “μορφοποίηση υπό όρους” και τα κελιά με πρώτους αριθμούς χρωματίζονται.

Χρωματίζονται τα κελιά που περιέχουν πρώτους αριθμούς

Μορφοποίηση υπό όρους. Χρωματίζονται τα κελιά που περιέχουν πρώτους αριθμούς

Σημειώσεις:
(*) Μπορείτε να δοκιμάσετε κάθε τμήμα του τύπου. Γράψτε το ή αντιγράψτε το στο φύλλο σας βάζοντας ίσον (=) μπροστά. Δηλαδή για να δείτε τι επιστρέφει ο πίνακας
 ROW(INDIRECT("1:"&INT(SQRT(A1))))
γράψτε τον σε ένα κελί του φύλλου έτσι:
 =ROW(INDIRECT("1:"&INT(SQRT(A1))))
Κατόπιν επιλέξτε το κελί και πατήστε F2 και κατόπιν F9. Πατήστε Esc για να φύγετε. Φυσικά, πρέπει να υπάρχει ένας αριθμός στο κελί Α1. Για το τμήμα αυτό του τύπου και για τον αριθμό 50 στο κελί Α1, θα δείτε:
 ={1\2\3\4\5\6\7}
 ή
 ={1;2;3;4;5;6;7}
ανάλογα με τους διαχωριστές που χρησιμοποίει ο υπολογιστής σας (Δέστε το προηγούμενο σημείωμα του ιστολογίου: “Απαραίτητες διευκρινίσεις για τους διαχωριστές ορισμάτων (Separators)”
(**) Η μετατροπή του πίνακα των λογικών τιμών σε αριθμητικές μπορεί να γίνει και με άλλους τρόπους όχι μόνο με το πλην(-). Μπορεί να γίνει με την συνάρτηση =Ν() που μετατρέπει τις λογικές τιμές TRUE και FALSE σε 1 και 0 αντίστοιχα, ή με πολλαπλασιασμό με 1*(…..) ή με δύο διαδοχικά πλην –(…..). Σε όλες αυτές τις περιπτώσεις θα εξισώσετε το τελικό άθροισμα με το 1 και όχι με το -1.
(***) Φυσικά η άθροιση μπορεί να γίνει και με την SUM, αλλά τότε η τελική συνάρτηση θα πρέπει να εισαχθεί σαν συνάρτηση-πίνακας με Ctrl+Shift+Enter για να μπορέσει να γίνει υπολογισμός των εσωτερικών πινάκων. Η SUMPRODUCT που από το σχεδιασμό της δέχεται σαν ορίσματα πίνακες, μπορεί να τους υπολογίσει χωρίς να έχει ανάγκη να εισαχθεί με Ctrl+Shift+Enter.
Τέλος μία VBA συνάρτηση που να αποφαίνεται αν ένας αριθμός είναι πρώτος, ίσως εξυπηρετεί καλύτερα και είναι εύκολο να γραφτεί, ακολουθώντας τον ίδιο αλγόριθμο. Αλλά η συνάρτηση φύλλου μας έδωσε τη ευκαιρία να συζητήσουμε ενδιαφέρουσες τεχνικές για συναρτήσεις που ήταν ο κύριος σκοπός του σημερινού σημειώματος.
Function isPrime(Number As Double) As Boolean
Application.Volatile
Dim x As Double
If Number <> Int(Number) Then isPrime = CVErr(xlErrValue)
isPrime = False
Select Case Number
 Case 0, 1
 Case Else
 For x = 2 To Int(Sqr(Number))
 If Int(Number / x) = Number / x Then GoTo telos
 Next
 isPrime = True
End Select
telos:
End Function
This entry was posted in excel, Μορφοποίηση υπό όρους, Συναρτήσεις φύλλου, Συναρτήσεις Χρήστη and tagged , , , , . Bookmark the permalink.

6 Responses to Συνάρτηση φύλλου για πρώτους αριθμούς

  1. Ο/Η Stazybο Hοrn λέει:

    Παραλλάσσοντας, με τη MOD() και με συνάρτηση-πίνακα, γλyτώνουμε το διπλό υπολογιστικό φόρτο της indirect() :

    ={OR(A1=2;A1=3;AND((MOD(A1;ROW(INDIRECT("2:"&INT(SQRT(A1)))))<>0)))}

  2. Ο/Η vioannis λέει:

    Ακούγεται πολύ λογικό αυτό που λες, για τη συνάρτηση που έστειλες (και σε ευχαριστώ πολύ γι αυτό). Αλλά, θα τις υποβάλω και τις δύο σε τεστ χρονομέτρησης και μετά θα ανακηρύξουμε νικητή!

  3. Ο/Η Stazybο Hοrn λέει:

    Αν υπολογίσεις και τη floating point διαίρεση που γλυτώνεις, δεν νομίζω ότι χρειάζεται χρονομέτρηση.

    Με την ευκαιρία, δες κι αυτό, αν θες. Ωραίο το μπλογκ σου, συνέχισε την καλή δουλειά!

  4. Ο/Η vioannis λέει:

    Πράγματι, φίλε Stazybo Horn, η ωραία συνάρτηση που έστειλες είναι πιο γρήγορη.
    Σε ένα φύλλο, στο οποίο όρισα τον υπολογισμό μη αυτόματο, στα κελιά Α1:Α15000 τοποθέτησα τους αριθμούς 10.000.000 έως 10.014.999 και στα κελιά Β1:Β15000 την Ctrl+Shift+Enter συνάρτηση σου

    =OR(A1=2;A1=3;AND((MOD(A1;ROW(INDIRECT("2:"&INT(SQRT(A1)))))0)))
    

    Κατόπιν έτρεξα την παρακάτω μακροεντολή:

    Sub test()
    t1 = VBA.Timer
    Application.Calculate
    t2 = VBA.Timer
    MsgBox t2 - t1
    End Sub
    

    Ο χρόνος υπολογισμού, στα 4-5 πειράματα που έκανα, ήταν από 11,9 sec έως 12,1sec.
    Για την συνάρτηση:

    =IF(A1=1;FALSE;SUMPRODUCT(-(A1/ROW(INDIRECT("1:"&INT(SQRT(A1))))=INT(A1/ROW(INDIRECT("1:"&INT(SQRT(A1)))))))=-1)
    

    οι χρόνοι ήταν από 17,1 έως 17,3 sec.
    Έχουμε λοιπόν, νικητή!
    Δούλεψα σε ένα φορητό υπολογιστή σε excel 2010.

  5. Ο/Η Stazybο Hοrn λέει:

    Το ίδιο τεστ σε μένα βγάζει πολύ μεγαλύτερη διαφορά: 4,9 έναντι 9,4 sec, αντίστοιχα. Εννοείται ότι έκλεινα το excel τελείως πριν από κάθε τρέξιμο, αλλιώς δεν ξέρουμε τι υπολογισμούς κασάρει…

  6. Ο/Η vioannis λέει:

    Φυσικά, ceteris paribus έγιναν και σε μένα τα δύο τεστ. Ευχαριστώ για το πολύ ενδιαφέρον link που έστειλες, θα το προσθέσω στο σχετικό σημείωμα του ιστολογίου “Εικονογραφημένη επικύρωση

Τα σχόλια είναι απενεργοποιημένα.