Prim Zahlen mit java

[walljumper]

bin noch anfänger also net lachen.

public class CPrimzahl
{
public static void main(String[] args)
{
int z;
int i;
int e;
double f;
double y;

for(z = 0; z <= 1000; z++)
{
for(i = 2; i <= z-1; i++)
{
e = z/i;
f = z/i;
y = f/e;


if(y == 1)
{
break;
}
System.out.println(z);
}
}

}
}


funktionieren tut das programm aber es spukt keine primzahlen aus.

So sollte es funktionieren:
wenn ich die zu testende zahl teile speichere ich das ergebnis einem als int und als double wert, wenn ich die beiden teile und das ergebnis 1 ist kann es keine prim zahl sein.


Was läuft falsch??
wird der int wert e in einen double wert umgewandelt??

 

[Morphium]

Mal abgesehen davon, dass die Laufzeit des Algorithmus katastrophal ist (nicht böse gemeint), sind da einige Fehler drin.

Punkt1: Du mußt nicht alle Zahlen <=z-1 testen, sondern nur alle Zahlen <= Wurzel(z) (Theorem aus der Zahlentheorie).

Auch solltest du "/" nicht verwenden, sondern "%" für die Modulo-Rechnung. Damit ersparst du dir nämlich die Double-Variablen und weitere Rechenzeit.

Versuch's mal damit: http://pimpf.pi.informatik.tu-darms...ung04/primzahltest/lsg/Primzahltest.java.html

 

[walljumper]

naja abschreiben will ich eigentlich nicht

Mal abgesehen davon, dass die Laufzeit des Algorithmus katastrophal ist (nicht böse gemeint), sind da einige Fehler drin.

Is ja auch mein erstes program^^

aber trotzdem danke für deine hilfe

 

[Limit]

Ein paar kleine Tipps:

1. break ist sehr unschön, wenn du nicht weißt, wie lange deine Schleife durchlaufen soll, dann benutz lieber eine while/repeat-Schleife statt einer for-Schleife.

2. Wie Morphium schon sagte, du musst nur bis Wurzel(z) testen. Das ist formal nicht ganz so einfach zu erklären, aber erahnen kann man es ganz gut. Du willst wissen, ob z eine Primzahl ist und testest alle möglichen Teiler von 2 bis z-1 durch. Aber wenn du jetzt eine Zahl größer Wurzel(z) testest und du bekämst ein glattes Ergebnis, müsste dieses ja kleiner Wurzel(z) sein, aber wenn die Zahl kleiner Wurzel(z) ist, hättest du sie ja schon getestet.

3. Eine weitere Möglichkeit deine Algorithmus zu beschleunigen wäre es z.B. den kleinen Satz von Fermat anzuwenden, dann folgendes gilt:

a^(z-1) mod z = 1 für a beliebige natürliche Zahl und z Primzahl.

Wenn also keine 1 rauskommt, ist es garantiert keine Primzahl, wenn 1 rauskommt, könnte es eine sein, muss es aber nicht.

 

[walljumper]

danke für die tipps

 

[CharlieB]

wenn du nicht gerade nach der neusten grössten Primzahl suchst,
ist ein "Streichalgorithmus" immer schneller als andere "Rechenalgorithmen"

Schau mal in deinem Matheduden unter "Sieb des Eratosthenes" nach

 

[xxXdEpHiLXxx]

Hey,

Also ich habe es so gelöst:
Habe Primzahlen auf null gesetzt und dan die anderen Zahlen ausgegeben.

public class PrimZahlen {

static int i;
static int m;
static int e;
static int p;

static void Primzahlen(int Arraylänge) {

int [] Array = new int [Arraylänge];
for (i = 0; i < Arraylänge; i++)
{
Array = i;
}
for (e = 2; e < 5000; e++)
{
for (m = e + e; m < Arraylänge; m = m + e)
{
Array[m] = 0;
}
}
for (p = 0; p < Arraylänge; p++)
{
if (Array[p] != 0)
System.out.println(Array[p]);
}
}
public static void main(String[] args) {
Primzahlen(10000);
}
}


Könnt ja mal sagen ob das ok ist ^^

Phil