C# Learning

Τι είναι το Sieve of Eratosthenes;

Φαντάσου ότι έχεις μια μεγάλη λίστα αριθμών και θέλεις να βρεις ποιοι από αυτούς είναι πρώτοι αριθμοί. Οι πρώτοι αριθμοί είναι αριθμοί που μπορούν να διαιρεθούν μόνο με το 1 και με τον εαυτό τους. Για παράδειγμα, το 2, το 3, το 5 και το 7 είναι πρώτοι αριθμοί.

Ο Sieve of Eratosthenes είναι μια έξυπνη μέθοδος για να βρεις όλους τους πρώτους αριθμούς μέχρι έναν συγκεκριμένο αριθμό. Είναι σαν να περνάς κάθε αριθμό από ένα φίλτρο για να δεις αν είναι πρώτος ή όχι.

Πώς Λειτουργεί;

1. Ξεκινάμε με όλους τους αριθμούς:
   • Φτιάχνουμε μια λίστα με όλους τους αριθμούς από το 2 μέχρι τον μεγαλύτερο αριθμό που θέλουμε να ελέγξουμε.
2. Φιλτράρουμε:
   • Ξεκινάμε από τον μικρότερο αριθμό και σημαδεύουμε όλους τους πολλαπλασιαστές του ως μη πρώτους.
   • Επαναλαμβάνουμε τη διαδικασία για τον επόμενο μη σημαδεμένο αριθμό μέχρι να ελέγξουμε όλους τους αριθμούς.
3. Τελικά, οι μη σημαδεμένοι αριθμοί είναι οι πρώτοι.

Παράδειγμα σε C#

Ας δούμε πώς να υλοποιήσουμε το Sieve of Eratosthenes στην C# για να βρούμε όλους τους πρώτους αριθμούς μέχρι έναν συγκεκριμένο αριθμό.

1. Δημιουργία του Προγράμματος:

using System;

class Program
{
    // Μέθοδος για να βρούμε όλους τους πρώτους αριθμούς μέχρι ένα συγκεκριμένο αριθμό
    static void SieveOfEratosthenes(int limit)
    {
        // Δημιουργούμε έναν πίνακα boolean για να κρατήσουμε αν ένας αριθμός είναι πρώτος ή όχι
        bool[] isPrime = new bool[limit + 1];

        // Αρχικοποιούμε όλους τους αριθμούς ως πρώτους
        for (int i = 2; i <= limit; i++)
        {
            isPrime[i] = true;
        }

        // Φιλτράρουμε τους αριθμούς
        for (int p = 2; p * p <= limit; p++)
        {
            if (isPrime[p] == true)
            {
                // Σημαδεύουμε όλους τους πολλαπλασιαστές του p ως μη πρώτους
                for (int i = p * p; i <= limit; i += p)
                {
                    isPrime[i] = false;
                }
            }
        }

        // Εμφανίζουμε τους πρώτους αριθμούς
        Console.WriteLine("Πρώτοι αριθμοί μέχρι το " + limit + ":");
        for (int p = 2; p <= limit; p++)
        {
            if (isPrime[p])
            {
                Console.Write(p + " ");
            }
        }
        Console.WriteLine();
    }

    static void Main(string[] args)
    {
        // Δοκιμάζουμε με το όριο 30
        SieveOfEratosthenes(30);
    }
}

Τι Κάνουμε Εδώ:

1. Δημιουργούμε Πίνακα:
   • isPrime: Ένας πίνακας boolean που κρατάει αν κάθε αριθμός είναι πρώτος ή όχι.
2. Αρχικοποιούμε Πίνακα:
   • Σημαδεύουμε όλους τους αριθμούς ως πρώτους στην αρχή.
3. Φιλτράρουμε:
   • Χρησιμοποιούμε την μέθοδο του Ερατοσθένη για να σημαδέψουμε τους πολλαπλασιαστές κάθε αριθμού.
4. Εμφανίζουμε Αποτέλεσμα:
   • Εμφανίζουμε όλους τους αριθμούς που δεν έχουν σημαδευτεί και είναι πρώτοι.

Συνοπτικά

• Sieve of Eratosthenes: Είναι μια μέθοδος για να βρούμε όλους τους πρώτους αριθμούς μέχρι έναν συγκεκριμένο αριθμό, χρησιμοποιώντας ένα φίλτρο για να απορρίψουμε τους μη πρώτους.
• C#: Χρησιμοποιούμε κώδικα C# για να εφαρμόσουμε αυτήν τη μέθοδο και να βρούμε τους πρώτους αριθμούς.