Primzahlen berechnen: Wie funktioniert das Sieb des Eratosthenes und der Code dafür?

Primzahlen berechnen..bin noch anfänger XD Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden Zum Anfang der Seite springen
hallo

ich soll ein programm in C# schreiben mit dem sich primzahlen errechnen lassen. die errechneten zahlen sollen einmal in ein Array und die nichtprim zahlen in ein anderes array, welche später in listboxen ausgegeben werden.

ich hab mich ein wenig im inet erkundigt und bin auf das sieb des eratosthenes gestoßen, welches ich iwie teilweise umsetzen konnte. leider weiß ich nicht warum es so funktioniert. hier mal der Code.

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
using System.Collections;

namespace Primzahlenrechner {
public partial class Form1:Form {
public Form1() {
InitializeComponent();
}


ArrayList primzahlen=new ArrayList();
ArrayList nichtprimz=new ArrayList();



private void b_primzahl_Click(object sender,EventArgs e) {

int grenze=Convert.ToInt32(tb_grenze.Text);


for(int zahl=2;zahl<grenze;zahl++) {
if(zahl%2!=0&&zahl%3!=0&&zahl%5!=0&&zahl%7!=0) {
primzahlen.Add(zahl);
lb_primFuellen();
}
}
}

void lb_primFuellen() {
lb_prim.Items.Clear();

for(int i=0;i<primzahlen.Count;i++) {
lb_prim.Items.Add(primzahlen[i]);

}

}

}
}

ich weiß da sind sicher noch fehler drin. jedoch funzt es und ich würd gern wissen wieso. als erklärung warum ich 2,3,5,7 genommen habe: da alle zahlen vielfache von ihnen sein können und sich somit als primzahlen ausschließen (hoffe ihr checkt was ich meine)

jedenfalls: tipps wie ich den code verbessern könnte bräucht ich und ob ihr noch einfacherer methoden kennt....am besten so das ich selbst drauf kommen kann und nicht direkt ALLES vorgeben Augenzwinkern wäre super nett...wie gesagt hab grad erst damit angefangen bisschen mit C# zu arbeiten und ist auch meine erste programmiersprache (naja HTML ein wenig Zunge raus (Ätsch) )...

mfg

sebattosai

nummer 1. Punkt Nummer 6

nummer 2.
Was willst du jetzt wissen, wie das Sieb funktioniert oder warum dein Code funktioniert?

Gruß Cookiie

hehe beides 😉 also ich hab mich etwas am Sieb des E. orientiert. aber warum mein code jetzt doch funzt ist mir wunderlich..

jedenfalls gibt mir mein prog auch nur alle elemente von 11 an aus..also 2,3,5 und 7 fehlen..

Hallo,
sofern du nur kleine Primzahlen (bis 1 Mio.) berechnen willst, kann man durchaus auch Brute Force verwenden.
Also testen, ob eine Zahl durch 2 teilbar ist, und wenn nicht, ob eine Zahl zwischen 3 bis sqrt(Zahl) teilbar ist, wobei man in 2er Schritten vorgeht.

Dein Code testet ja nur, ob eine Zahl durch 2, 3, 5 oder 7 teilbar ist, was machst du aber bei 13*11 = 143?
143 wäre bei dir eine Primzahl.

Sonst noch hier eine super Anleitung für das Sieb:
Algorithmus der Woche: Das Sieb des Eratosthenes

also wie schon erwähnte im thread namen: ich bin totaler anfänger und komm noch nicht ganz klar mit den ganzen dingen. hab mir zwar schon paar dinge angeeignet aber die logischen abläufe hängen bei mir noch teilweise im keller bzw kommen nur schleppend oder mit hilfe von kollegen.

und ne wirkliche antwort find ich im inet bisher auch nich, daher mein thread hier 😉

wäre schön, wenn ihr mir schon ne reihenfolge posten könntet, die ich abarbeiten müsste..damit ich wenigstens mit meinen bisherigen kenntnissen voran komme...

mfg

wenn du es auf hardcore machst

zähler der von 2 bis grenze hochzählt
primarraylist[0] = 2
if zähler/ primarray = teilbar
keine primzahl
else
primzahl, add to primarray

mehr ist es nicht, wird halt je nach grenze sehr umfangreich.

Gruß Cookiie

Hi,

Schau mal unter Sieb des Eratosthenes. Dort ist das sieb im allgebeinen gut und einfach erklärt (Speziell in der grafik).
Zur umsetztung in das Programm würde ich dir empfehlen, ein bool array mit ausdehnung = obergrenze anzulegen, alle elemente mit true initialiesieren und es gilt dann: (Index+2) = Wert, true : primzahl false keine Primzahl.
Index + 2 da Primzahlen ab 2 und Array ab 0 losgeht

mfg dechavue

jo das auf wiki kenn ich und hab ich auch schon selbst belesen. allerdings schaffe ich es nicht das auf ne code zu übertragen geschweige die ganzen vorschläge die ihr macht zu raffen. entweder bin ich total blöd oder ich hab einfach noch keinen zugang gefunden wie ich mein hirn so einstellen kann um in einer programmiersprache zu denken -.-

ich drücks mal so aus: bitte vereinfacht das vllt noch etwas 😉 sonst versteh ich erstmal nur bahnhof XD

aber danke schon mal an alles zuvor

Also grundlegende vergleiche und abfragen mit if solltest du beherrschen, da du wirklich daran scheiterst, zumindest scheint es so.
Empfehle ich dir mal folgendes Buch Visual C# 2005.
In dem Buch ist alles wichtige und die Grundlagen der Objektorientierten Programmierung sehr gut anhand von Beispielen erklärt. Arbeite dich da erstmal ein wenig durch und dann schauen wir weiter. Vorher bringt das glaub ich nicht viel.

und jetzt schönen Feierabend an alle^^.
Cookiie

Hallo,
die Brute Force Variante:

bool IsPrim(int x) {
  int max = (int)Math.sqrt(x);
  if(x%2==0 && x>2)
     return false;
  
  for(int i=3;i<=max;i+=2)
     if(x%i== 0)
       return false;


   return true;
}

void GetPrims() { 
   List<int> prims = new List<int>();
   List<int> noPrims = new List<int>();

   for(int i=2;i<1000;++i)
       if(IsPrim(i))
         prims.Add(i); 
       else
         noPrims.Add(i);
}

Dann, hier meine Sieb des Eratosthenes Implementierung:

public static List<int> SiebDesEratosthenes(int N)
        {
            if (N > 400000000)
                return BitSiebDesEratosthenes(N);
            else
                return ByteSiebDesEratosthenes(N);              
        }

        //Bit flags
        private static List<int> BitSiebDesEratosthenes(int N)
        {
            BitArray nichtPrim = new BitArray(N >> 1, false);
            int max = ((int)Math.Floor(Math.Sqrt(N))) >> 1;
            List<int> prims = new List<int>();
         

            for (int i = 1; i < max; )
            {
                int p = PrimFromIndex(i);

                int lastPrim = N / p;
                int index = (lastPrim - 1) >> 1;

                while (nichtPrim[index])
                    index--;

                for (int k = index; k >= 0 && ((k << 1) + 1) >= p; )
                {                    
                    int produkt = p * PrimFromIndex(k);
                    nichtPrim[PrimToIndex(produkt)] = true;

                    //PriorPrim
                    while (nichtPrim[--k]) ;

                }

                //NextPrim
                while (nichtPrim[++i]) ;
            }
            //return null;
            for (int i = 0; i < nichtPrim.Length; i++)
                if (!nichtPrim[i])
                    prims.Add(PrimFromIndex(i));

            return prims;
        }

        //Bool-Array
        private static List<int> ByteSiebDesEratosthenes(int N)
        {
            bool[] nichtPrim = new bool[N >> 1];
            int max = ((int)Math.Floor(Math.Sqrt(N))) >> 1;
            List<int> prims = new List<int>();
          
           
            for (int i = 1; i < max; )
            {
                int p = PrimFromIndex(i);

                int lastPrim = N / p;
                int index = (lastPrim - 1) >> 1;

                while (nichtPrim[index])
                    index--;

                for (int k = index; k >= 0 && ((k << 1) + 1) >= p; )
                {                   
                    int produkt = p * PrimFromIndex(k);
                    nichtPrim[PrimToIndex(produkt)] = true;

                    //PriorPrim
                    while (nichtPrim[--k]) ;
                }

                //NextPrim
                while (nichtPrim[++i]) ;
            }
        
            for (int i = 0; i < nichtPrim.Length; i++)
                if (!nichtPrim[i])
                    prims.Add(PrimFromIndex(i));

            return prims;
        }

        private static int PrimFromIndex(int i)
        {
            if (i == 0)
                return 2;
            else
                return (i << 1) + 1;
        }

        private static int PrimToIndex(int prim)
        {
            if (prim == 2)
                return 0;
            else
                return (prim-1) >> 1;
        }

Klasse für Primzahl- und Integer-Berechnungen

guten morgen,

also ich arbeite weiter am primproblem...leider kann ich mit den riesigen code strukturen von euch auch nich grad viel anfangen, da ich kaum Code davon verstehe. ich kenn schon die eigenschaften von if-abfragen, variablen (bool = true or false) und schleifen..mein hauptproblem is einfach selbst einen logischen weg aufzubauen, wie ich das erreiche was ich ja will: primzahlen ausrechnen. ich kenne auch die eigenschaften von primzahlen (nur durch 1 und sich selbst etc), lässt sich ja nachlesen. aber wie ich es dann codiere ins C# damit ich primzahlen damit ausrechnen kann ist mir iwie zu hoch.

habt ihr ein einfacheres beispiel worauf ich vllt aufbauen könnte um mein problem zu lösen...???

(PS: ich habe ein handbuch zu C#, also bitte nichts mehr dazu posten..benutze GuideToCSharp...is verständlich für mich 😉 )

wäre euch sehr dankbar dafür

mfg

Andavos hat doch schon beide Möglichkeiten gepostet. Die Brut-Force-Variante ist wirklich sehr sehr übersichtlich und sollte wirklich leicht verständlich sein.
Das Sieb des Eratosthenes ist nunmal von Natur aus komplexer und damit auch der entsprechende Programmcode, da gibt es nicht wirklich einen Leichteren. Du wirst dich wohl oder übel damit auseinander setzen müssen oder einen anderen Algorithmus probieren müssen. Wobei das Sieb noch einer der leichteren ist.

Gruß Curatio

okay könntest du mir dann kurz kommentieren was er in der brute force variante mit dem bool anstellt?

sonst versteh ich die rechnung glaub ich soweit. aber was dann genau mit den werten passiert bzw wie er dann auf die prim kommt ist mit schleierhaft...

mfg

Original von Andavos

  
    bool IsPrim(int x) //Bsp. x = 141  
    {  
        int max = (int)Math.sqrt(x); //Teiler von 141 können nicht grösser als 141^(1/2) sein, deshalb wird der grösste "Teiler" als die Wurzel von 141 definiert  
        if (x % 2 == 0 && x > 2) //Wenn x(141) eine gerade Zahl ist dann soll false zurückgegeben werden, ausser wenn x=2 is, da 2 die einzige gerade Primzahl ist, die es gibt.  
            return false;  
  
        for (int i = 3; i <= max; i += 2) //Eine Schleife wird gestartet, i = 3, und es wird immer i += 2 gerechnet, da eine gerade zahl, die höher als 2 ist sowieso nie eine Primzahl ist. i < max, da max der maximale Teiler ist  
            if (x % i == 0) //Wenn x durch i teilbar ist, dann wird false zurückgegeben.  
                return false;  
  
  
        return true; //x hat keine Teiler ausser sich selbst und ist deshalb eine Primzahl  
    }  

hab nur schnell alles kommentiert, der code hat übrigens nicht immer richtig, eins wird als primzahl angeschaut, obwohl es keine ist, das kannst du aber noch relativ einfach abfangen...

mfG b3nJ

seufz, also er fängt mit GetPrims an

void GetPrims() {
   // 2 Listen werden angelegt, sollte klar sein
   List<int> prims = new List<int>();
   List<int> noPrims = new List<int>();
   
   // schleife von 2 -999, wenn isPrim true liefert der prim-liste zuordnen, bei false entsprechender der anderen Liste
   for(int i=2;i<1000;++i)
       if(IsPrim(i))
         prims.Add(i);
       else
         noPrims.Add(i);
}

aufruf von isPrim mit übergabe der jeweiligen zahl

bool IsPrim(int x) {
  int max = (int)Math.sqrt(x);  // maximal bis wurzel der zahl probieren, weil 2*3 = 3*2 
  if(x%2==0 && x>2)
     return false;
  
  for(int i=3;i<=max;i+=2)
     if(x%i== 0)
       return false;


   return true;
}

x%i <-- modulo-operator, so mehr verrat ich jetzt nicht, sonst lernst nix