Online Γεννήτρια Πρώτων Αριθμών

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

Ένας πρώτος αριθμός είναι ένας φυσικός αριθμός μεγαλύτερος του 1, ο οποίος διαιρείται μόνο με το ένα και τον εαυτό του. Οι μικρότεροι πρώτοι αριθμοί είναι οι 2, 3, 5, 7, 11, 13, 17, 19, 23, 29… Ο αριθμός 2 είναι ο μοναδικός άρτιος πρώτος αριθμός – όλοι οι άλλοι άρτιοι αριθμοί διαιρούνται με το δύο.

Αριθμοί όπως οι 4 (= 2 × 2), 6 (= 2 × 3) ή 15 (= 3 × 5) δεν είναι πρώτοι αριθμοί – τους λέμε σύνθετους αριθμούς.

Πώς λειτουργεί η γεννήτρια;

Για την εμφάνιση όλων των πρώτων αριθμών σε ένα εύρος, χρησιμοποιούμε το Κόσκινο του Ερατοσθένη – έναν από τους αρχαιότερους και πιο αποδοτικούς αλγορίθμους, που περιέγραψε ο Έλληνας μαθηματικός Ερατοσθένης από την Κυρήνη περίπου το 240 π.Χ.

Ο αλγόριθμος διαγράφει διαδοχικά τα πολλαπλάσια κάθε πρώτου αριθμού που βρίσκει. Ό,τι απομένει είναι οι πρώτοι αριθμοί. Όλος ο υπολογισμός γίνεται απευθείας στον περιηγητή σας – κανένα δεδομένο δεν αποστέλλεται στον διακομιστή.

Για την τυχαία επιλογή, η γεννήτρια δημιουργεί αρχικά μια λίστα με όλους τους πρώτους αριθμούς στο εύρος και στη συνέχεια επιλέγει τυχαία τον απαιτούμενο αριθμό από αυτήν, χρησιμοποιώντας μια κρυπτογραφικά ασφαλή γεννήτρια (crypto.getRandomValues()).

Λειτουργίες της γεννήτριας

• Όλοι οι πρώτοι αριθμοί – εμφανίζει κάθε πρώτο αριθμό στο καθορισμένο εύρος (έως 10.000)
• Τυχαία επιλογή – επιλέγει N τυχαίους πρώτους αριθμούς από το εύρος (κατάλληλο για μεγάλα εύρη)
• Ταξινόμηση – ταξινομεί τα αποτελέσματα σε αύξουσα σειρά
• Διαχωριστικό – επιλέξτε πώς θα διαχωρίζονται οι αριθμοί κατά την αντιγραφή
• Γρήγορες προεπιλογές – τα πιο συνηθισμένα εύρη με ένα κλικ

Πού χρησιμοποιούνται οι πρώτοι αριθμοί;

Κρυπτογραφία και ασφάλεια

Οι πρώτοι αριθμοί αποτελούν το θεμέλιο της σύγχρονης κρυπτογραφίας. Αλγόριθμοι όπως ο RSA λειτουργούν με την αρχή ότι το γινόμενο δύο μεγάλων πρώτων αριθμών είναι εύκολο να υπολογιστεί, αλλά η αντίστροφη παραγοντοποίηση σε πρώτους παράγοντες είναι υπολογιστικά πολύ απαιτητική.

• Κρυπτογράφηση RSA – τα κλειδιά παράγονται από δύο μεγάλους πρώτους αριθμούς
• Diffie-Hellman – ανταλλαγή κλειδιών πάνω από μια πρώτο-αριθμητική μονάδα
• Συναρτήσεις κατακερματισμού (Hash functions) – πρώτοι αριθμοί ως μαγικές σταθερές (SHA, MD5)

Μαθηματικά και επιστήμη

• Θεωρία αριθμών – τα βασικά δομικά στοιχεία των ακεραίων αριθμών
• Εικασία του Γκόλντμπαχ – κάθε άρτιος αριθμός > 2 μπορεί να εκφραστεί ως το άθροισμα δύο πρώτων αριθμών (ακόμα αναπόδεικτο)
• Υπόθεση του Ρίμαν – ένα από τα προβλήματα του Χίλμπερτ, αφορά την κατανομή των πρώτων αριθμών

Πρακτικές εφαρμογές

• Πίνακες κατακερματισμού (Hash tables) – το μέγεθος του πίνακα ως πρώτος αριθμός μειώνει τις συγκρούσεις
• Γεννήτριες ψευδοτυχαίων αριθμών – γραμμική σύγκλιση με πρώτο-αριθμητική μονάδα
• Μουσική και ρυθμός – πολυρρυθμίες με μήκη κύκλων πρώτων αριθμών

Κατανομή των πρώτων αριθμών

Οι πρώτοι αριθμοί κατανέμονται ακανόνιστα μεταξύ των φυσικών αριθμών, αλλά η πυκνότητά τους μειώνεται με την αύξηση του εύρους. Αυτό περιγράφεται από το Θεώρημα Πρώτων Αριθμών: ο αριθμός των πρώτων μέχρι το N είναι περίπου N / ln(N).

Το Κόσκινο του Ερατοσθένη βήμα προς βήμα

Εύρος 2–30:
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]

1. Επιλέξτε το 2, διαγράψτε τα πολλαπλάσια: 4, 6, 8, 10, 12...
2. Επιλέξτε το 3, διαγράψτε τα πολλαπλάσια: 9, 15, 21, 27...
3. Επιλέξτε το 5, διαγράψτε τα πολλαπλάσια: 25...
4. √30 ≈ 5.5 → ολοκληρώθηκε

Πρώτοι αριθμοί: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

Το Κόσκινο του Ερατοσθένη σε κώδικα

JavaScript

function sieve(to) {
  const composite = new Uint8Array(to + 1);
  const primes = [];
  for (let p = 2; p <= to; p++) {
    if (composite[p]) continue;
    primes.push(p);
    for (let j = p * p; j <= to; j += p) composite[j] = 1;
  }
  return primes;
}

Python

def sieve(n):
    composite = bytearray(n + 1)
    primes = []
    for p in range(2, n + 1):
        if not composite[p]:
            primes.append(p)
            for j in range(p * p, n + 1, p):
                composite[j] = 1
    return primes

Συχνές ερωτήσεις (FAQ)