4. Generierung von Zahlen im Sieb des Eratosthenes (Coprimzahlen)

Generierung von Zahlen im Sieb des Eratosthenes (Coprimzahlen)

  • ?

    Hallo Leute! Ich habe ein kleines Problem mit meiner Implementierung des Sieb des Eratosthenes. Ich fürchte, ich muss dazu ein bisschen ausholen (wer die Einführung nicht lesen will, kann ja zu tl;dr springen 😃 ):
    In meinem Sieb schaue ich mir nicht ALLE Zahlen (oder nur alle ungeraden Zahlen) an, sondern nur die Zahlen, die die Bedingng Prod∗k+IProd*k+I erfüllen.
    Wie das zustande kommt:

    • Wähle aus, wie viele Primzahlen als "Basis" genommen werden (zB. 3)
    • Ermittle die ersten Primzahlen (mit 3: prim = {2,3,5} )
    • Multipliziere diese Primzahlen =: Prod (hier: prod = 30)
    • Ermittle alle Zahlen I, die kleiner als Prod sind und Coprim zu Prod, also gcd(i,Prod)=1 für i=1...prod (hier: I = {1,7,11,13,17,19,23,29} )

    Alle Zahlen, die als Primzahlen in Frage kommen, haben also die Form prod∗k+Iprod*k+I. Oder wie in dem Beispiel: 30∗k+1,7,11,13,17,19,23,2930*k + {1,7,11,13,17,19,23,29}.
    Hier meine Implementierung dazu:

    for(unsigned k = 0; ; k+=prod)							//prod ist das produkt der erten n Primzahlen
{
	for(unsigned i= k==0?1:0; i<CoPrimes.size(); ++i)	//CoPrimes ist eine Liste, mit allen Zahlen < prod, die Coprim zu prod sind
	{
		unsigned next = k + CoPrimes[i];				//generiere alle Zahlen der Form prod*k+I

		if(next*next > max)
			break;										//Algorithmus ist fertig

		if(all[next])									//erstes Auftauchen der Zahl "next" im array ALLER zahlen "all" -> "next" ist Primzahl
			for(unsigned j=next*next; j<=max; j+=next)	//hier ist mein Problem
				all[j]=0;								//Siebe alle Vielfachen von next aus
	}
}

    Mein Problem liegt in Zeile 11: Ich möchte ja alle Vielfachen der Zahlen aus prod*k+I aussieben, die Primzahlen sind. Allerdings werden in meiner Implementation von oben wirklich alle Vielfachen dieser Zahl ausgesiebt. Ich möchte aber nur alle Vielfache aussieben, die auch die Bedingung prod*k+I erfüllen (sonst gewinne ich mit diesem Algorithmus ja nichts 😃 ).
    Beipsiel:

    prod = 30
I = {1,7,11,13,17,19,23,29}

11 wurde als Primzahl identifiziert: also k=0 und I=11

streiche alle Vielfachen von 11, die die Bedingung 30*k+I erfüllen:

In der aktuellen implementierung werden folgende Zahlen gestrichen:
121, 132,143, 154, 165, 176, 187 usw

Es sollen aber nur gestrichen werden:
121 (k=4, I=1), 143 (k=4, I=23), 187 (k=6, I=17), usw

    Gibt es dazu vielleicht eine geschlossene Form, wie ich dieses Vielfache bestimmen kann?

    tl;dr:
    Wie generiere ich alle Vielfachen einer Zahl prod*k+I, die selbst nur Teil aller Zahlen aus prod*n+I sind (k,n natürliche Zahlen, I ist Liste aller Coprimzahlen zu prod, die kleiner als prod sind)?

    Ich hoffe das war einigermaßen verständlich 🙂

    0
  • V

    Keine Ahnung, ob ich es richtig verstanden habe. Ich versuche es mal.

    MultiPrim schrieb:

    [*] Wähle aus, wie viele Primzahlen als "Basis" genommen werden (zB. 3)

    std::cin

    MultiPrim schrieb:

    [*] Ermittle die ersten Primzahlen (mit 3: prim = {2,3,5} )

    bool isPrime(int n);
    nebst vector::push_back

    MultiPrim schrieb:

    [*] Multipliziere diese Primzahlen =: Prod (hier: prod = 30)

    for über den vector, hätte es allerdings schon im letzten Punkt miterledigt

    MultiPrim schrieb:

    [*] Ermittle alle Zahlen I, die kleiner als Prod sind und Coprim zu Prod, also gcd(i,Prod)=1 für i=1...prod (hier: I = {1,7,11,13,17,19,23,29} )

    int gcd(int a,int b);
    anderervector.push_back
    Ergebnis: anderercecot={1,7,11,13,17,19,23,29}

    MultiPrim schrieb:

    Alle Zahlen, die als Primzahlen in Frage kommen, haben also die Form prod∗k+Iprod*k+I. Oder wie in dem Beispiel: 30∗k+1,7,11,13,17,19,23,2930*k + {1,7,11,13,17,19,23,29}.

    for (i=0;;++i)
   for each s in anderervector
      print i*30+s

    bzw

    for (i=0;;++i)
   for each s in anderervector
      streichImErathostenesFeldAlleVielfachenVon i*30+s
    0
  • ?

    Hm, dann hast du das falsch verstanden 😃
    Das Programm steht und funktioniert auch. Aber im vorliegenden Programm streiche ich alle Vielfachen der Primzahl und nicht alle Vielfachen, die der "prod*k+I" Regel folgen. Schau dir nochmal das Beispiel an: im aktuellen Fall streiche ich ALLE Vielfache von 11:

    121, 132,143, 154, 165, 176, 187, 198, 209, 220 usw

    Allerdings sind darunter Zahlen, die per Definition keine Primzahlen sein können:
    zB lassen sich 132, 154,1 65, 176 nicht darstellen in der Form "30k+{1,7,11,13,17,19,23,29}". Es ist also unnötig, die extra zu streichen (das tue ich dann erst später).
    Ich möchte erstmal nur alle Zahlen streichen, die auch meine Bedinung "prod    k+I" erfüllen können, namentlich
    121 (k=4, I=1), 143 (k=4, I=23), 187 (k=6, I=7) usw.

    0
Anmelden zum Antworten