Primzahlen: ein paar offene Fragen

[alex2345]

Habe folgendes Programm hier im Forum über Primzahlen gefunden, zu dem ich aber noch ein paar Fragen hätte. Es funktioniert wunderbar aber ich blicke nicht ganz durch:

public class Primzahlentest
{

    private int[] primes;
    private int found;

    public boolean isPrim(int n) 
    { 

        if (n <= 1) return false;

        if (n == 2) return true;

        if (n % 2 == 0) return false;

        for (int p = 3; p * p <= n; p += 2)
            if (n % p == 0)
                return false;

        return true;

    }

    public int[] getFirstPrims(int k)
    {
        primes = new int[k];
        primes[0] = 2;
        primes[1] = 3;

        for (int index = 2; index < k; index++)
        {
            boolean found = false;

            for (int n = primes[index - 1] + 2; !found; n += 2)
            {
                for (int i = 1; true; i++)
                {
                    int p = primes[i];
                    if (found = p * p > n)
                    {
                        primes[index] = n;
                    }
                    if (n % p == 0) break;
                }
            }
        }
        return primes;
    }

}

for (int p = 3; p * p <= n; p += 2) boolean isPrim liefert ja true oder false bei einer eingegebenen Zahl zurcük. Für 2 und alle geraden Zahlen ist dies ja fix definiert. Wieso wird p=3 definiert? Und wieso nehme ich dann das Quadrat von p und überprüfe ob es <= n ist?

Wieso wird bei getFirstPrim found in der ersten for-Schleife auf false gesetzt?
Im Gegensatz zum oberen Teil wo ja überprüft wird ob p * p <= n wird im unteren p * p > n überprüft. Beide funktionieren einwandfrei, obwohl ja das Gegenteil überprüft wird. Wieso ist das so?
Wenn man checkstyle benutzt sagt es dass man "inner assignments" vermeiden soll. Dieses Problem tritt in dieser Zeile auf: if (found = p * p > n) Was passt daran nicht?

 

[SlaterB]

> Wieso wird p=3 definiert?

ab 3 muss überprüft werden, für 1 und 2 sowie alle geraden Zahlen ist das Ergebnis schon bekannt

> Und wieso nehme ich dann das Quadrat von p und überprüfe ob es <= n ist?

bis zur Wurzel von n sind alle interessanten Teiler untersucht,
Beispiel 100, es reicht die Zahlen 3-10 zu untersuchen,

der Teiler 20 ist beispielweise irrelevant, da der Gegenteiler 5 (20*5 = 100) dann schon vorher gefunden worden wäre

> Wieso wird bei getFirstPrim found in der ersten for-Schleife auf false gesetzt?

weil dessen Bedeutung pro Schleifendurchlauf neu errechnet werden soll,
das ist doch was ganz grundlegendes,

stell dir vor du suchst im Telefonbuch nach 'Schmidt' und findest den Namen oder auch nicht (true/false),
dann suchst du nochmal, diesmal nach 'Müller',
dabei willst du doch nicht das Ergebnis der vorherigen Suche miteinfließen lassen,
also alles zurück auf Grundstellung


> Beide funktionieren einwandfrei, obwohl ja das Gegenteil überprüft wird. Wieso ist das so?

if (a < b) und if (b > a) sehen auch entgegengesetzt aus, aber das hat doch nichts zu sagen,
zudem kann man fomulieren "solange x gilt, bleibe am Ball" und "wenn x nicht gilt dann höre auf",

eine einzelne Bedingung hat noch keine wichtige Bedeutung,
erst der Gesamtzusammenhang bestimmt den Sinn

mit solchen Fragen mache ich mir jetzt aber nicht die Mühe, die sehr komplexe Methode getFirstPrims(int k) überhaupt selber zu verstehen, die hat es in sich

 

[alex2345]

Danke