Primzahlen

[witch doctor]

Ich habe mal ein kleines Primzahlen Programm geschrieben, nur irgendwie funktioniert das nicht.

Er gibt alle Zahlen aus.

Hier der Code:

import java.io.*;


public class aufgab10

{

	public static void main(String args[])

	throws IOException

	{

		BufferedReader din = new BufferedReader(new InputStreamReader(System.in));


		int n=0;

		boolean prim = true;


		System.out.println("Bitte geben Sie die Obergrenze ein");

		n = Integer.parseInt(din.readLine());		


		for(int i=2; i<=n; i++)

		{

			for(int j=2;j<=i;j++)

			{

				if(i%j==0)

				 prim=false;

				prim=true;


			}


			if(prim==true)

			{

				System.out.println(+i);

			}

		}

	}

}

[/php]

Packe ich das jedoch in eine Funktion, klappt das ganze.

Ich verstehe jedoch nicht, warum das mit den beiden Schleifen nicht läuft.

Hier der Code mit Funktion zum Vergleich:

[php]
import java.io.*;

public class aufgabe10f
{
static boolean prim(int x)

{
for (int j = 2; j<x; j++)
if (x%j==0)
return false;
return true;


}

public static void main(String args[])
throws IOException
{
BufferedReader din = new BufferedReader(new InputStreamReader(System.in));

int n=0;


System.out.println("Bitte geben Sie die Obergrenze ein");
n = Integer.parseInt(din.readLine());

for(int i=2; i<=n;i++)
{
if(prim(i))
System.out.println(+i);
}
}
}

Ich danke euch schon mal für die Hilfe!

[Der Kleine]

Original geschrieben von witch doctor

for(int j=2;j<=i;j++)

{

if(i%j==0)

prim=false;

prim=true;

}

Also be deiner if(i%j==0) - Anweisung fehlen IMHO geschweifte Klammern.

Du fragst if - ab und dannach setzt du prim für alle vorgänge wieder auf true.

Probiers mal mit

if(i%j==0)

  {

      prim=false;

  }

else

  {

      prim=true;

  }

[Goos]

Original geschrieben von Der Kleine

Also be deiner if(i%j==0) - Anweisung fehlen IMHO geschweifte Klammern.

Du fragst if - ab und dannach setzt du prim für alle vorgänge wieder auf true.

Probiers mal mit

if(i%j==0)

  {

      prim=false;

  }

else

  {

      prim=true;

  }

Uiuiui das halt ich aber fuer bedenklich, weil da ja Primzahlen die schon als keine erkannt wurden wieder auf true gesetzt werden beim naechsten Durchlauf.

Es ist zwar alles andere als eine optimierte Primzahlenermittlung aber ich wuerde wenn schon, dann im ersten Beispiel das prim=true ganz weglassen, dann klappt das auch.

Ach und Witch Doctor.... in deinem zweiten Beispiel solltest auch noch n paar Klammern setzen. Es ist zwar richtig so, aber schaut schrecklich aus und ist somit viel schwerer nachzuvollziehen.

Goos

[witch doctor]

Also wenn ich die Klammern auch setze, bekomme ich das selbe Resultat.

So funktioniert es, aber ich weiß nicht warum

import java.io.*;


public class aufgab10

{

	public static void main(String args[])

	throws IOException

	{

		BufferedReader din = new BufferedReader(new InputStreamReader(System.in));


		int n=0;

		boolean prim = true;


		System.out.println("Bitte geben Sie die Obergrenze ein");

		n = Integer.parseInt(din.readLine());		


		for(int i=2; i<=n; i++)

		{

			for(int j=2;j<i;j++)

			{


				if(i%j==0)

  				{

      				prim=false;

  				}


			}


			if(prim==true)

			{

				System.out.println(+i);

			}

		}

	}

}[/php]

Kann mir jemand erklären, warum das so funktioniert?

[Goos]

Na weil du das prim=true weggelassen hast.

So wie das zu anfang noch drin war wurde wenn eine Zahl als Nicht-Primzahl entlarvt war die gleich Zahl im naechsten Durchgang wieder auf Primzahl = TRUE gesetzt. Wie sollte das so denn dann auch funktionieren koennen?

Goos

[witch doctor]

Ach so klar! Schon verstanden!

Danke euch allen!!

[Nalimov]

Und wenn Du für große Zahlen den Code noch etwas verbessern willst, dann lass die Variable j nur bis Wurzel i laufen. Das reicht völlig aus. (Die Theorie nennt man glaube ich Sieb des Erathosthenes, oder so).

D.h. willst Du testen ob 5739 eine Primzahl ist dann reicht es, ganzzahlige Teiler bis sqrt(5739), also bis 75 zu untersuchen.

Noch effektiver wird es, wenn Du erst den Test durch 2 machst und nach dem 1. ungeraden Teiler (3) in zweiersprüngen vorgehst. Ist die Zahl nämlich nicht durch zwei teilbar, dann auch nicht durch andere gerade Zahlen...

So kannst Du den Code noch etwas effizienter gestalten.

(Ist ja auch ein Unterschied ob deine innere Schleife, wie in obigem Beispiel 5738mal oder nur 37mal durchlaufen wird)