the Prime Question

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

Το μικρότερο σύνολο αριθμών που περιέχει όλους τους πρώτους αριθμούς είναι το {1, 2, 3, 6n±1} όπου n οποιοσδήποτε φυσικός. Δηλαδή πρώτοι είναι οι 1, 2, 3 και κάποιοι από τους αριθμούς της μορφής 6n±1. Αυτό δεν σημαίνει ότι είναι όλοι οι αριθμοί που παράγονται με αυτόν τον τρόπο, αλλά σίγουρα όσοι δεν παράγονται δεν είναι πρώτοι. Μπορούμε να αποκλείσουμε έτσι με ασφάλεια τα ⅔ των πιθανοτήτων και να φτιάξουμε έναν αλγόριθμο που θα χρειάζεται το ⅓ του αρχικού χρόνου.

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

#include <math.h>

int isPrime(int num)
{
    int tmp;
    int i;
    if (num < 4)
        return 1;
    if (((num+1)%6==0) || ((num-1)%6==0)) {
        tmp = (int)sqrt((float)num);
        for (i = 3; i <= tmp; i+=2 )
            if ( num % i == 0 ) return 0;
        return 1;
    }
    return 0;
}

Προφανώς δεν γίνονται έλεγχοι αν η παράμετρος num είναι σωστή (αρνητικοί, μηδέν) θεωρώντας ότι αυτός που θα το χρησιμοποιήσει ξέρει το πρόβλημα και σε τι πλαίσια λειτουργεί. Η function isPrime επιστρέφει 0 για τους αριθμούς που δεν είναι πρώτοι και 1 για όσους είναι. Δεν χρειάζεται να ελέγξει για τα 1,2,3 αφού είναι ήδη γνωστά (σαν εξαίρεση του pattern 6n±1) και ελέγχει μόνο όσους ακολουθούν αυτό το pattern. Οσοι δεν το ακολουθούν είναι γνωστό ότι δεν είναι πρώτοι (πετάμε τα ⅔ των πιθανοτήτων) και τελικά με τις διαιρέσεις θα κάνουμε τον τελικό έλεγχο που καθυστερεί και περισσότερο. Φυσικά δεν χρειάζεται εδώ να ελέγξουμε για τους ζυγούς αριθμούς αφού είναι γνωστό ότι δεν θα είναι ζυγός κάποιος από τους διαιρετέους – κανένας ζυγός δεν δίνει πολλαπλάσιο που να είναι μονός αριθμός.

Κάποια στιγμή αργότερα ίσως να ξαναβουτήξω σε μαθηματικά νερά για να δω τι βελτιστοποιήσεις μπορούν να γίνουν, να ξεκαθαρίσω την απορία μου αφού έχω δει το 1 άλλοτε να θεωρείται πρώτος, άλλοτε όχι και να βάλω τα σχετικά links.