Υπολογιστής Πρώτων Αριθμών

Υπολογιστής Πρώτων Αριθμών - Άθροισμα, Πλήθος & Εύρεση Πρώτων

🔢 Υπολογίστε το άθροισμα πρώτων αριθμών, βρείτε πρώτους σε εύρος, ελέγξτε αν ένας αριθμός είναι πρώτος και βρείτε τον ν-οστό πρώτο. Γρήγορος αλγόριθμος Κοσκίνου του Ερατοσθένη με οπτικοποίηση.

Τι είναι οι πρώτοι αριθμοί;

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

Οι πρώτοι 25 πρώτοι αριθμοί

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

Πώς να ελέγξετε αν ένας αριθμός είναι πρώτος

Μέθοδος 1 - Δοκιμαστική διαίρεση:

• Ελέγξτε αν το n διαιρείται με κάποιον αριθμό από 2 έως √n
• Αν ναι, είναι σύνθετος (όχι πρώτος)
• Αν όχι, είναι πρώτος

Παράδειγμα: Είναι το 17 πρώτος;

• √17 ≈ 4,12, άρα ελέγχουμε διαιρετότητα με 2, 3, 4
• 17 ÷ 2 = 8,5 (δεν διαιρείται)
• 17 ÷ 3 = 5,67 (δεν διαιρείται)
• 17 ÷ 4 = 4,25 (δεν διαιρείται)
• Αποτέλεσμα: Το 17 είναι πρώτος!

Κόσκινο του Ερατοσθένη

Αρχαίος αλγόριθμος για να βρείτε όλους τους πρώτους έως το n:

• Βήμα 1: Καταγράψτε όλους τους αριθμούς από 2 έως n
• Βήμα 2: Σημειώστε το 2 ως πρώτο και διαγράψτε όλα τα πολλαπλάσιά του
• Βήμα 3: Βρείτε τον επόμενο μη διαγραμμένο αριθμό (3) και σημειώστε τον ως πρώτο
• Βήμα 4: Διαγράψτε όλα τα πολλαπλάσια αυτού του πρώτου
• Βήμα 5: Επαναλάβετε μέχρι √n
• Αποτέλεσμα: Όλοι οι μη διαγραμμένοι αριθμοί είναι πρώτοι

Άθροισμα πρώτων αριθμών

Άθροισμα των πρώτων n πρώτων:

• Πρώτοι 10: 2+3+5+7+11+13+17+19+23+29 = 129
• Πρώτοι 100: Άθροισμα = 24.133
• Πρώτοι 1000: Άθροισμα = 3.682.913

Άθροισμα πρώτων έως το n:

• Έως 10: 2+3+5+7 = 17
• Έως 100: Άθροισμα = 1.060
• Έως 1000: Άθροισμα = 76.127

Θεώρημα των πρώτων αριθμών

Το πλήθος των πρώτων μικρότερων του n είναι περίπου n/ln(n):

• Έως 100: ~25 (πραγματικό: 25)
• Έως 1.000: ~145 (πραγματικό: 168)
• Έως 10.000: ~1.086 (πραγματικό: 1.229)
• Έως 100.000: ~8.686 (πραγματικό: 9.592)

Τύποι πρώτων αριθμών

Δίδυμοι πρώτοι: Πρώτοι που διαφέρουν κατά 2

• (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43)...

Πρώτοι του Μερσέν: Μορφή 2ᵖ - 1 όπου p είναι πρώτος

• 2² - 1 = 3
• 2³ - 1 = 7
• 2⁵ - 1 = 31
• 2⁷ - 1 = 127
• Ο μεγαλύτερος γνωστός πρώτος είναι Μερσέν (24,8 εκατ. ψηφία!)

Πρώτοι της Sophie Germain: Πρώτος p όπου 2p+1 είναι επίσης πρώτος

• 2 (2×2+1 = 5), 3 (2×3+1 = 7), 5 (2×5+1 = 11), 11, 23, 29...

Πρώτοι του Φερμά: Μορφή 2^(2ⁿ) + 1

• F₀ = 3, F₁ = 5, F₂ = 17, F₃ = 257, F₄ = 65.537
• Γνωστοί μόνο 5 πρώτοι του Φερμά

Εφαρμογές των πρώτων αριθμών

Κρυπτογραφία (RSA):

• Βασίζεται στη δυσκολία παραγοντοποίησης μεγάλων αριθμών
• Χρησιμοποιεί δύο μεγάλους πρώτους (εκατοντάδες ψηφία)
• Ασφαλίζει online τραπεζικές συναλλαγές, email και ιστοσελίδες

Πίνακες κατακερματισμού:

• Μεγέθη πρώτων μειώνουν συγκρούσεις
• Χρήση σε βάσεις δεδομένων και caching

Παραγωγή τυχαίων αριθμών:

• Οι πρώτοι δημιουργούν καλύτερες ψευδο-τυχαίες ακολουθίες
• Χρήση σε προσομοιώσεις και παιχνίδια

Ενδιαφέροντα στοιχεία

• Απειρία: Αποδείχθηκε από τον Ευκλείδη ~300 π.Χ. – οι πρώτοι δεν τελειώνουν
• Κενά: Μπορούν να είναι αυθαίρετα μεγάλα
• Εικασία Goldbach: Κάθε άρτιος > 2 είναι άθροισμα δύο πρώτων (ανεπίλυτο!)
• Υπόθεση Riemann: Βραβείο 1 εκατ. δολαρίων για απόδειξη σχετικά με την κατανομή
• Κενά πρώτων: Η διαφορά διαδοχικών πρώτων αυξάνεται
• Πιθανότητα: Τυχαίος αριθμός n έχει ~1/ln(n) πιθανότητα να είναι πρώτος

Ρεκόρ

• Μεγαλύτερος γνωστός πρώτος: 2^82,589,933 - 1 (2018, 24.862.048 ψηφία)
• Μεγαλύτεροι δίδυμοι πρώτοι: 2.996.863.034.895 × 2^1.290.000 ± 1
• Υπολογισμός: GIMPS (Great Internet Mersenne Prime Search) κατανεμημένο έργο

Συχνές παρανοήσεις

• Το 1 ΔΕΝ είναι πρώτος: Με τον σύγχρονο ορισμό (ακριβώς 2 διαιρέτες)
• Δεν είναι όλοι οι περιττοί πρώτοι: 9, 15, 21, 25... είναι σύνθετοι
• Τύπος για όλους τους πρώτους: Δεν υπάρχει απλός τύπος που να παράγει όλους τους πρώτους
• Μοτίβο στους πρώτους: Δεν υπάρχει προβλέψιμο μοτίβο (φαίνονται τυχαίοι)

💡 Συμβουλή: Για να ελέγξετε αν ένας μεγάλος αριθμός είναι πρώτος, αρκεί να ελέγξετε διαιρετότητα μέχρι την τετραγωνική ρίζα του! Π.χ. για το 997, ελέγξτε μέχρι √997 ≈ 31,6: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31. Αν κανένα δεν διαιρεί ακριβώς, είναι πρώτος! Επίσης, εκτός από 2 και 3, όλοι οι πρώτοι είναι της μορφής 6k±1.