Wie ist das unter dem Code zur Identifizierung von Primzahlen [geschlossen] - Java, Primzahlen

Dies ist der Code, der die Primzahlen bis zur angegebenen Zahl identifiziert. Wenn Sie beispielsweise 7 eingeben, enthält die zurückgegebene ArrayList alle ersten 7 Primzahlen.

    public static ArrayList<Integer> calcPrime(int inp)
{
ArrayList<Integer> arr = new ArrayList<Integer>();
arr.add(2);
arr.add(3);

int counter = 4;

while(arr.size() < inp)
{
// 23 and 25
if(counter % 2 != 0 && counter%3 != 0)
{
int temp = 4;
while(temp*temp <= counter)
{
if(counter % temp == 0)
break;
temp ++;
}
if(temp*temp > counter)
{
arr.add(counter);
}
}
counter++;
}

return arr;
}

Meine Frage ist das. Ich verstehe, dass dieser Code alle Zahlen filtert, die durch 2 und 3 teilbar sind. Bei allen anderen Zahlen, z. B. 23 oder 25, werden nur die Quadrate der Zahlen von 4 verwendet.

Ich möchte wissen, wie dies sein Ziel erreicht. Bitte helfen Sie mir, das zu verstehen.

Antworten:

2 für die Antwort № 1

Der Teil, der die Überprüfung durchführt, ist der folgende:

                if(counter % temp == 0)
break;

Es ist überhaupt nicht auf die Quadrate der Zahlen angewiesen. Das sagt nur, wann man aufhört, die Zahlen zu überprüfen.

Zuerst werden einige Einstellungen vorgenommen. Es weiß, dass 2 und 3 Primzahlen sind, und fügt sie seiner Liste hinzu.

Ab 4 wird dann geprüft, ob es sich bei der Zahl um eine Primzahl handelt. Wenn dies der Fall ist, wird es dem Array hinzugefügt. Wenn dies nicht der Fall ist, wird es übersprungen und die nächste Nummer überprüft.

"Überprüft also, ob die Zahl eine Primzahl ist" wird durchgeführt von: überprüfe zuerst, ob es durch 2 oder durch 3 teilbar ist:

    if(counter % 2 != 0 && counter%3 != 0)

Dann mache ich ab 4 wieder den gleichen Check: Ist meine potenzielle Primzahl (counter) durch diese Zahl teilbar (temp)

        if(counter % temp == 0)

Wenn dies der Fall ist, handelt es sich nicht um eine Primzahl break befehle und prüfe den nächsten counter um zu sehen, ob das eine Primzahl ist.

Ob counter ist nicht teilbar durch temp es erhöht sich temp und prüft erneut. Wann temp ist so groß, dass es sich nicht lohnt zu überprüfen, ob es sich um einen Faktor handelt. Der Algorithmus weiß das counter ist eine Primzahl und fügt sie der Liste hinzu.

Das temp*temp Das liegt daran, dass beim Überprüfen, ob eine Zahl eine Primzahl ist, nicht alle Zahlen bis zu überprüft werden müssen counter. ob temp*temp ist größer als unser Ziel, dann für temp um ein Faktor zu sein, muss der andere Faktor kleiner sein als temp, und es wurde bereits geprüft.

---

0 für die Antwort № 2

% bedeutet Rest, wenn durch geteilt, und ist das Snippet, das die eigentliche Arbeit erledigt. Wenn der Rest Null ist, wird er genau geteilt, sodass die Zahl keine Primzahl ist.

Der quadratische Teil ist, weil Sie ein wenig optimieren können, indem Sie nur die Zahlen berücksichtigen, die kleiner als die Quadratwurzel sind (denn wenn eine Zahl größer ist als die Quadratwurzel, ist das Ergebnis Weniger als die Quadratwurzel und sollte früher gefangen worden sein)

---