Anzahl Primzahlen im Intervall

[Ghosthuman1]

Hi,
Ich habe folgende aufgabe ich soll in einem bestimmten Intervall (1, 100) alle Primzahlen finden.
das Programm läuft, aber ich soll noch dafür sorgen dass, mein Programm nicht so lange brauch um das ganze anzuzeigen. Code:

public class PrimTest {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int zuTesten = 16;
		System.out.println("die Zahl[" + zuTesten + "]ist eine Primzahl:"
				+ isPrimzahl(zuTesten));

		System.out.println(" So viele Primzahlen gibt es im Intervall: "
				+ Primzaehl(1, 10));
		// TODO Auto-generated method stub

	}

	public static boolean isPrimzahl(int zuTesten) {
		boolean i = true;
		int a = zuTesten;
		for (a = 2; a < zuTesten; a++) {
			int p = zuTesten % a;
			if (p == 0) {
				i = false;
			}

		}

		return i;
	}

	public static int Primzaehl(int b, int c) {
		int a = 0;
		int z = 0;

		for (a = b; a <= c; a++) {
			if (isPrimzahl(a)) {
				z++;
			}
		}
		return z;

	}
}

schon jetzt danke für Hilfe
Ghosthuman

 

[Gast2]

Du möchtest keine Hilfe, sondern, dass jemand die Arbeit für dich erledigt. Das gehört somit ins Hausaufgaben Forum.

Hilfe gibts bei ner Frage zu einem benannten Problem. Dabei reicht es nicht zu sagen: "Ist noch nicht schnell genug"

 

[Landei]

Du gehst die ganze Schleife durch, selbst wenn du im ersten Durchlauf schon die Antwort weisst. Stattdessen solltest du den "frühen Ausgang" benutzen ("early exit strategy")

    public static boolean isPrimzahl(int zuTesten) {
        int a = zuTesten;
        for (a = 2; a < zuTesten; a++) {
            int p = zuTesten % a;
            if (p == 0) {
                return false;
            }
        }
        return true;
    }

Natürlich kann man das noch weiter verbessern, z.B. nur ungerade Werte außer der 2 testen, oder nur bis zur Wurzel des Kandidaten testen.

Am effektivsten für einen Bereich von Primzahlen ist natürlich ein Sieb (wie das von Eratosthenes), aber dann müsstest du dein ganzes Programm umbauen.

Allerdings kann ich mir nicht vorstellen, dass dein jetziges Programm für kleine Bereiche unter 1000 zu langsam sein sollte, falls du das nicht gerade auf einem Zuse 3 laufen lässt...

 

[pro2]

Mal Sieb des Eratosthenes ? Wikipedia anschauen ggf.