Primzahlen mit Array errechnen!

[bpblub]

Guten Tag/Nacht,

unzwar lerne ich in der Schule Javaprogrammierung und wir haben jetzt die Aufgabe gestellt bekommen, ein Programm zu schreiben, das Primzahen errechnet mit Arrays.
Ok!
Meine Idee:
Ich nehme als erstes die Zahl 2 und nehme die immer wieder +2 und setze die Arrays die die 2 trifft auf 0,sagen wir mal bis 10000. Danach setze ich die 3 und nehme die immer +3, das bis 10000 und dann nehme ich die 4 und nehme die immer +4 ... das bis 10 und dann dürfte ich genug ausgesiebt haben.

So das Programm was ich schon geschrieben hab:

static int a = 10001;
static int[] AStack= new int [a];

public static void eingabe()
{
for(it i=1;i<y;i++)
{
AStack[i] = i;
}
}

public static void rechnen()
{
int z=10;
for(int d=2;d<z;d++)
{
    for(int e=0;e<y;e=d+d)
    {
    AStack[e] = 0;
    }
}

public static void ausgeben()
{
for(int u=1;u<y;u++)
{
if(AStack[u] = 0)
{}
else
{
System.out.Println(AStack[u]);
}
}
}

public static void main ( String[] args )
{
eingabe();
rechnen();
ausgeben();
}

so ok, ich hoffe das Programm ist so ok geschrieben, ich kann es gerade nicht Prüfen, hab es ausn Kopf auf der Arbeit rausgeschrieben.
Jetzt kommt aber das Problem, die ersten 10 werden nicht ausgeben, also 2,3,5 und 7. Ist ja auch nur logisch, aber wie ich das Sinnvoll ändern kann?
Jetzt zu euch, könnt ihr mir ein Tipp geben ?
Ich möchte keine Lösung eher ein Hinweis oder Tipp ; )

Vielen Dank schonmal im Vorraus.
lg
blub ; )

 

[angelchr]

hi,
also ich kann deinen Gedankengängen nicht folgen. 2 dann immer plus ?? 3 dann immer plus.. ?? 2 ist eine primzahl 3 auch 4 ist keine? Was genau machst du?
Google mal nach "sieb des erasthotenes" viellecht hilft dir das weiter

Gruß
Angelchr

 

[bpblub]

Also ich will einfach nur wenn ich bei der Zahl 2 bin immer +2 machen, weil dann immer
2,4,6,8 ... rausfallen würde und das setze ich auf 0, damit ich es dann aussortieren kann ...

Genau das selbe bei 3
3,6,9,12,15 ... die würden dann auf 0 gesetzt werden und würden dann automatisch ausgesiebt werden ...

Bei 4:
4,8,12,16 ... wobei das bei 2 schon alles rausfällt ...

bei 5:
5,10,15,20,25 ... wird dann auf 0 gesetzt ...

meine Bedinung ist das ja, solange Array 0 ist soll er nichts machen und wenn in den Array eine Zahl ist, die nicht 0 ist, dann soll er sie ausgeben, das war meine Grundidee.

lg
blub ; )

 

[0x7F800000]

Der Tipp mit dem Sieb von Erasosthenes war exakt :toll: danach solltest du wirklich mal googln...

hier hab ich sogar meinen alten code aus irgendeiner übung rausgekramt:

import java.io.*;

public class SieveOfEratosthenes {

public static void main(String[] args){
	
	boolean[] marker=new boolean[2];
	int arrayLength=0;
	
	//read the length of array
	BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
	boolean correctInput=false;
	while(!correctInput){
		correctInput=true;
		System.out.println("Geben Sie die Obergrenze an:");
		try{
			arrayLength=Integer.parseInt(reader.readLine());
			if(arrayLength<0){
				System.out.println("negative arraylänge???");
				correctInput=false;
			}
		}catch(IOException e){
			System.out.println(e);
			correctInput=false;
		}catch(NumberFormatException e){
			System.out.println(
					"Zahlformat ungueltig. Geben Sie eine Naturliche Zahl ein."+
					" Die Zahl sollte nicht groesser als "+Integer.MAX_VALUE+" sein");
			correctInput=false;
		}
	}
	
	if(arrayLength>2){
		//allocate place for boolean values
		try{
			marker=new boolean[arrayLength];
		}catch(OutOfMemoryError e){
			System.out.println(
					"Rufen Sie bei der NASA an, die duerften"+
					" ein Paar Superrechner zu viel haben. Auf"+
					"diesem hier reicht der Speicher nicht aus");
		}
	}
	
	//initialize with "true"
	for(int i=0; i<marker.length; i++){
		marker[i]=true;
	}
	
	//mark 0 and 1: these are not primes, but 1 divides everything, /0 is undefined
	marker[0]=marker[1]=false;
	
	//sorting out reducible elements
	int maxDivisor=(int)Math.sqrt(arrayLength);
	for(int currentDivisor=0; currentDivisor<=maxDivisor; currentDivisor++){
		
		//if this one is already marked as not irreducible, continue 
		if(!marker[currentDivisor]){
			continue;
		}else{
			//mark all n>=currentDivisor^2, currentDivisor|n
			for(int n=currentDivisor*currentDivisor; 
					n<marker.length; n+=currentDivisor){
				marker[n]=false;
			}
		}
	}
	
	//print
	final int COLUMNS=10;
	int col=0;
	
	for(int i=0; i<marker.length; i++){
		if(marker[i]){
			System.out.printf(" %8d",i);
			col++;
			if(col>=COLUMNS){
				col=0;
				System.out.println();
			}
		}
	}
	
}
}

COLUMNS gibt lediglich an, in wievielen spalten die zahlen ausgegeben werden... sonst gibts dazu nichts zu sagen, steht alles bei wikipedia.

 

[kowa]

Mach es doch mit Division so wie der Eratosthenes das macht.

Anleitung von www.jjam.de/Java/Applets/Primzahlen/Eratosthenes.html:

1. Schreibe alle natürlichen Zahlen von 2 bis zu einer beliebigen Zahl n auf.
2. Streiche alle Vielfachen von 2 heraus.
3. Gehe zur nächstgrößeren nichtgestrichenen Zahl und streiche deren Vielfache heraus.
3. Wiederhole 3. sooft es geht.
4. Die übriggebliebenen Zahlen sind Primzahlen.

Ist so ähnlich wie deine Methode, wenn man 2 immer mit 2 addiert siebt man quasi auch "Nicht-Primzahlen" aus. Hier läuft es nur mit einer Division.

 

[bpblub]

ok, ich werd mich mal dahinter setzen, aber mein gedankegang ist doch nicht so ganz falsch oder ? Ich will es ja lernen und nicht gleich eine Lösung haben ; )

Vielen Dank für die Antworten, wie ich gepostet habe, war ok oder eher nicht ?

lg
blub

 

[angelchr]

Der Ansatz deiner Lösung ist "nicht schlecht" allerdings nicht effizient. Wie du schon selber gesagt hast berechnest du sehr vieles doppelt. Der Algrorithmus von Eratosthenes ist anfangs recht langsam und wird dann immer schneller. Deiner ist Konstant langsam. Dazu kommt noch dass eine Multiplikation mit 2 eindeutig schneller ist wie ein plus 2... Rein effizienztechnisch gesehen, da eine multiplikation mit einem Bitshift realisiert wird.

Gruß
angelchr

 

[bpblub]

Vielen Dank ; )

 

[Marco13]

Dazu kommt noch dass eine Multiplikation mit 2 eindeutig schneller ist wie ein plus 2... Rein effizienztechnisch gesehen, da eine multiplikation mit einem Bitshift realisiert wird.

... realisiert werden kann - ob das gemacht wird, und ob das schneller oder langsamer ist, als eine Addition sei mal dahingestellt :wink: (Ich würde addieren...)

 

[0x7F800000]

aber um etwas mit bitshifts zu multiplizieren, muss man:

1) den faktor als summe von zweierpotenzen darstellen: zählt nicht, weil alles in 2er potenzen gerechnet wird = 0 aufwand
2) für jede "1" in der zweierpotenz einen bitschift durchführen: n mal wenn insgesamt n-mal die "1" in der binärdarstellung des faktors vorkommt
3) für jede "1" eine summation von den bit-ge-shifteten zahlen ausführen, also n mal die addition

=> um ein produkt zu berechnen braucht man doch definitiv mindestens eine addition, und das ist sicherlich langsamer als einfach nur eine addition...


korrigiert mich wenn ich mir das irgendwie falsch vorstelle :roll:

 

[bpblub]

ah interessant, ich finde so diskussionen gut, da lernt man immer viel ; )
Ein Bitshift ist also ein kurz gesagt ein "guter" Algorithmus ?

lg
blub

 

[schalentier]

Aaahh... nu verwirrt den armen blub doch nicht. Ein Bitshift bedeutet, das die Bits einer Zahl verschoben werden.

int x = 2; // binaer: 0010
int y = x>>1; // Bitshift um 1 Bit nach rechts: 0001 (1 dezimal)
int z = x<<1; // nach links: 0100 (4 dez.)

Wie du siehst entspricht das verschieben um 1 Bit nach rechts der Division durch 2, ein Verschieben nach links der Multiplikation mit 2. Und das ist theoretisch schneller als die Multiplikation (bzw Division) - praktisch aber nur, wenn man das mit einer hardwarenahen Programmiersprache (z.b. C/C++) macht. Und selbst da sollte ein vernuenftiger Compiler ein "*2" durch ein "<<1" ersetzen.

Hat aber alles nichts mit deinem Primzahlenalgorithmus zu tun...

 

[Ark]

Ich finde dieses Sieben alles andere als effizient. Ich würde ausnutzen, dass als zu untersuchen notwendige Teiler nur die in Frage kommen, die höchstens so groß sind wie die Quadratwurzel aus der zu untersuchenden Zahl. Außerdem müssen nur die vorangegangenen Primzahlen im genannten Intervall zum Test herangezogen werden. So habe ich das jedenfalls in Erinnerung, könnte auch irren.

Ark

 

[0x7F800000]

Ein Bitshift bedeutet, das die Bits einer Zahl verschoben werden.

was what hast have du you jetzt said gesagt now? :bae:

ch würde ausnutzen, dass als zu untersuchen notwendige Teiler nur die in Frage kommen, die höchstens so groß sind wie die Quadratwurzel aus der zu untersuchenden Zahl.

jo, das hast du richtig in erinnerung:

int maxDivisor=(int)Math.sqrt(arrayLength);

aber um effizienz geht es hier nicht wirklich, mit so einem doofen sieb kann man eh niemals etwas nützliches aussieben, die primzahlen kannst du vieelicht in Ulam's Spirale reinzeichnen oder Pi(x) skizzieren... Für nützliche 2-3 Hunderstellige zahlen funktioniert es eh nicht mehr...