Primtalsalgoritm - Hitta alla primtal

🧠 Syfte

Varför bryr vi oss ens om primtal?

Jo, de är lite som byggstenarna i matematiken – alla andra tal kan byggas upp av dem! Det låter kanske lite torrt, men det har faktiskt enorm betydelse.

Primtal är grundläggande inom kryptografi (tänk säkerheten på dina banktransaktioner!), och de dyker upp i massor av andra områden inom matematik och datavetenskap. Så, att förstå hur man hittar dem effektivt är en riktigt användbar färdighet.

🔢 Vad är ett primtal?

Tänk dig ett tal. Är det bara delbart med 1 och sig självt? Då är det ett primtal! Enkelt, va? Till exempel är 2, 3, 5, 7 och 11 primtal. Men 4 (delbart med 2), 6 (delbart med 2 och 3), och 9 (delbart med 3) är inte primtal. 1 är ett specialfall – det räknas inte som ett primtal.

Vi ska nu lära oss att skriva kod som kan avgöra om ett tal är ett primtal eller inte. Redo?

✅ Checklista: Är talet ett primtal?

Låt oss skapa en enkel checklista för att avgöra om ett tal är ett primtal. Följ stegen noggrant!

1. Är talet <= 1? → Då är det inte ett primtal. Simplare än så blir det inte!
2. Är talet 2 eller 3? → Då är det ett primtal. 2 och 3 är våra två minsta primtal-hjältar!
3. Är talet jämnt (delbart med 2)? → Då är det inte ett primtal (utom 2, som vi redan kollat!). Jämna tal större än 2 har alltid 2 som delare.
4. Testa division – Börja från 3 och testa bara udda tal (vi har redan kollat jämna tal). Fortsätt testa delbarhet tills du når kvadratroten ur talet.

Varför kvadratroten? Tänk dig att 16 har en delare större än 4 (nämligen 4). Om det finns en delare större än kvadratroten, så måste det finnas en mindre delare också. Smart, eller hur?

1. Hittar du en delare? → Inte ett primtal. Grattis, du hittade en delare!
2. Ingen delare hittad? → Primtal! Du har hittat ett primtal! Ge dig själv en high five!

Låt oss testa med 17 (primtal) och 21 (inte primtal):

• 17: Inte <= 1, inte 2 eller 3, inte jämnt, ingen udda delare upp till sqrt(17) ≈ 4.12. Alltså: 17 är ett primtal!
• 21: Inte <= 1, inte 2 eller 3, inte jämnt, men delbart med 3 (7 x 3 = 21). Alltså: 21 är inte ett primtal.

🎨 Visuellt flödesschema

Här är ett flödesschema som visualiserar checklistan:

flowchart TD
  A[Start] --> B{Tal <= 1?};
  B -->|Ja| C[Inte primtal];
  B -->|Nej| D{Tal = 2 eller 3?};
  D -->|Ja| E[Primtal];
  D -->|Nej| F{Jämnt tal?};
  F -->|Ja| C;
  F -->|Nej| G{Testa udda delare upp till sqrt(n)};
  G -->|Hittade delare| C;
  G -->|Ingen delare| E;

💻 Grundläggande implementation

// Simple prime check function
bool IsPrimeBasic(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i = i + 6) {
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    }
    return true;
}

// Example usage
Console.WriteLine(IsPrimeBasic(17)); // True - 17 är ett primtal!
Console.WriteLine(IsPrimeBasic(21)); // False - 21 är inte ett primtal!

🚀 Optimerad version

Den tidigare algoritmen funkar bra för mindre tal, men blir långsam för stora tal. Låt oss optimera den!

// Optimized prime check
bool IsPrimeOptimized(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i = i + 6) { //Optimized loop increment
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

//Example usage:
Console.WriteLine(IsPrimeOptimized(17)); // True - 17 är ett primtal!
Console.WriteLine(IsPrimeOptimized(999983)); // True - Testa ett stort tal!

🧮 Sieve of Eratosthenes (Eratosthenes såll)

Vill du hitta alla primtal upp till ett visst tal? Då är Eratosthenes såll din bästa vän! Det är en otroligt effektiv algoritm som fungerar ungefär som att sålla bort alla icke-primtal.

Tänk dig att du har en massa stenar. Du tar bort alla stenar som är jämna (utom 2), sen alla som är delbara med 3 (utom 3), sen 5, osv. Stenarna som är kvar är primtalen!

//Sieve of Eratosthenes implementation
List<int> SieveOfEratosthenes(int limit) {
    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]) {
            for (int i = p * p; i <= limit; i += p) {
                isPrime[i] = false;
            }
        }
    }
    List<int> primes = new List<int>();
    for (int i = 2; i <= limit; i++) {
        if (isPrime[i]) {
            primes.Add(i);
        }
    }
    return primes;
}

//Example usage:
List<int> primes = SieveOfEratosthenes(50);
Console.WriteLine(string.Join(", ", primes)); //Skriver ut alla primtal upp till 50

😄 Obligatoriskt pappaskämt

Vad är ett primtals favoritdrink? En Prime-time martini! (Prime-time = bästa tiden).

Har du förstått detta har du kommit långt! Grattis!

Nu kan du börja koda som en galning! Skapa fler algoritmer och utforska nya möjligheter.