Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 | Suche | FAQ

Hauptmenü
myCSharp.de
» Startseite
» Forum
» Suche
» Regeln
» Wie poste ich richtig?

Mitglieder
» Liste / Suche
» Wer ist online?

Ressourcen
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Microsoft Docs

Team
» Kontakt
» Cookies
» Spenden
» Datenschutz
» Impressum

Primzahlen berechnen: Wie funktioniert das Sieb des Eratosthenes und der Code dafür?
sebattosai
myCSharp.de - Member



Dabei seit:
Beiträge: 6
Herkunft: Krefeld

Themenstarter:

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

beantworten | zitieren | melden

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
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von sebattosai am .
private Nachricht | Beiträge des Benutzers
Cookiie
myCSharp.de - Member

Avatar #avatar-2328.jpg


Dabei seit:
Beiträge: 364
Herkunft: früher Leipzig, jetzt Out of Rosenheim

beantworten | zitieren | melden

nummer 1. Punkt Nummer 6

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


Gruß Cookiie
"Hail to the King, Baby!"
private Nachricht | Beiträge des Benutzers
sebattosai
myCSharp.de - Member



Dabei seit:
Beiträge: 6
Herkunft: Krefeld

Themenstarter:

beantworten | zitieren | melden

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..
private Nachricht | Beiträge des Benutzers
Andavos
myCSharp.de - Member



Dabei seit:
Beiträge: 138

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
sebattosai
myCSharp.de - Member



Dabei seit:
Beiträge: 6
Herkunft: Krefeld

Themenstarter:

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
Cookiie
myCSharp.de - Member

Avatar #avatar-2328.jpg


Dabei seit:
Beiträge: 364
Herkunft: früher Leipzig, jetzt Out of Rosenheim

beantworten | zitieren | melden

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
"Hail to the King, Baby!"
private Nachricht | Beiträge des Benutzers
dechavue
myCSharp.de - Member

Avatar #avatar-2999.png


Dabei seit:
Beiträge: 180
Herkunft: Österreich

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
sebattosai
myCSharp.de - Member



Dabei seit:
Beiträge: 6
Herkunft: Krefeld

Themenstarter:

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
Cookiie
myCSharp.de - Member

Avatar #avatar-2328.jpg


Dabei seit:
Beiträge: 364
Herkunft: früher Leipzig, jetzt Out of Rosenheim

beantworten | zitieren | melden

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
"Hail to the King, Baby!"
private Nachricht | Beiträge des Benutzers
Andavos
myCSharp.de - Member



Dabei seit:
Beiträge: 138

beantworten | zitieren | melden

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;
        }
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Andavos am .
private Nachricht | Beiträge des Benutzers
Borg
myCSharp.de - Member



Dabei seit:
Beiträge: 1548
Herkunft: Berlin, Germany

beantworten | zitieren | melden

Klasse für Primzahl- und Integer-Berechnungen
private Nachricht | Beiträge des Benutzers
sebattosai
myCSharp.de - Member



Dabei seit:
Beiträge: 6
Herkunft: Krefeld

Themenstarter:

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
Cookiie
myCSharp.de - Member

Avatar #avatar-2328.jpg


Dabei seit:
Beiträge: 364
Herkunft: früher Leipzig, jetzt Out of Rosenheim

beantworten | zitieren | melden

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
"Hail to the King, Baby!"
private Nachricht | Beiträge des Benutzers
sebattosai
myCSharp.de - Member



Dabei seit:
Beiträge: 6
Herkunft: Krefeld

Themenstarter:

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
B3nj
myCSharp.de - Member

Avatar #avatar-2528.gif


Dabei seit:
Beiträge: 242
Herkunft: CH;SG

beantworten | zitieren | melden

Zitat
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
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von B3nj am .
private Nachricht | Beiträge des Benutzers
Cookiie
myCSharp.de - Member

Avatar #avatar-2328.jpg


Dabei seit:
Beiträge: 364
Herkunft: früher Leipzig, jetzt Out of Rosenheim

beantworten | zitieren | melden

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
"Hail to the King, Baby!"
private Nachricht | Beiträge des Benutzers