Ein Programm, das bestimmt, ob eine Zahl eine Primzahl oder eine nicht primäre Zahl ist. (Unterstützt C #, Java, C ++) Ich habe es gemacht, weil es bei Programmierwettbewerben wie CodeIQ oft als Problem auftritt.

Schnellstes Primzahl-Beurteilungsprogramm

C # -Version

public static bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; //Schließen Sie gerade Zahlen im Voraus aus

    double sqrtNum = Math.Sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            //Keine Primzahl
            return false;
        }
    }

    //Ist eine Primzahl
    return true;
}

Wenn möglich, möchte ich den Code in dem Bereich halten, den ich verstehen kann, daher verwende ich ihn derzeit als schnellste Version. (Es ist einfach, oder?) Ich bin jedoch der Meinung, dass diese Geschwindigkeit ausreicht, um das Problem zu lösen. Wenn dies nicht ausreicht, denken Sie noch einmal darüber nach.

"Eh, es ist ein Service, bringen Sie auch Java- und C ++ - Implementierungen mit!" * (Fast das gleiche)

Java-Version

public static boolean isPrime(int num) {
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; //Schließen Sie gerade Zahlen im Voraus aus

    double sqrtNum = Math.sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            //Keine Primzahl
            return false;
        }
    }

    //Ist eine Primzahl
    return true;
}

C ++ - Version

#include <math.h> 

bool IsPrime(int num)
{
	if (num < 2) return false;
	else if (num == 2) return true;
	else if (num % 2 == 0) return false; //Schließen Sie gerade Zahlen im Voraus aus

	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2)
	{
		if (num % i == 0)
		{
			//Keine Primzahl
			return false;
		}
	}

	//Ist eine Primzahl
	return true;
}

Java-Version Ich habe es nicht ausgeführt, aber ich denke, es ist in Ordnung. .. * *

Erklärung der mathematischen Begriffe

Ich werde kurz die Begriffe erklären, die ich nicht verstanden habe.

Was ist eine Primzahl? → Eine natürliche Zahl, die nicht durch andere Zahlen als 1 und Sie selbst teilbar ist
Was ist eine zusammengesetzte Zahl? → Andere Zahlen als Primzahlen

Erklärung des schnellsten Algorithmus

Für den implementierten Algorithmus habe ich hauptsächlich auf den Inhalt dieser Site verwiesen. Primzahlurteil|Algorithmus und Datenstruktur| Aizu Online Judge

Auf dieser Seite ** Bei der Beurteilung der Primzahl kann die Eigenschaft verwendet werden, dass "die zusammengesetzte Zahl x einen Primfaktor p hat, der p ≤ √ x erfüllt". ** ** ** Es gibt eine Beschreibung, "Die zusammengesetzte Zahl x hat einen Primfaktor p, der p ≤ x erfüllt." = "Wenn x eine zusammengesetzte Zahl ist, hat sie einen Bruchteil kleiner oder gleich √x" </ u> Mit anderen Worten, die Schleifenendbedingung ist bis zu Math.Sqrt (num). Im Vergleich zur einfachen Durchführung der Restberechnung bis zu num wird die Anzahl der Schleifen reduziert und die Verarbeitungsgeschwindigkeit stark reduziert.

Andere Algorithmen

Es scheint, dass es ungefähr zwei Arten von Algorithmen zur Beurteilung von Primzahlen gibt.

Entscheidende Methode zur Beurteilung der Primzahl --Probabilistische Primzahlbeurteilungsmethode

Die endgültige Beurteilungsmethode besteht darin, eine Primzahl nach einer Methode zu beurteilen, die sicherlich keinen Fehler verursacht. Das probabilistische Beurteilungsverfahren ist ein Verfahren, bei dem die Beurteilungsgeschwindigkeit dramatisch erhöht wird, obwohl gelegentlich Fehler auftreten können.

Der Vertreter der endgültigen Primzahlbeurteilungsmethode ist die "AKS-Primzahlbeurteilungsmethode". Eine typische probabilistische Primalitätsbeurteilungsmethode ist der "Miller-Rabin-Primalitätstest".

Wenn Sie eine schnellere Implementierung benötigen, sollten Sie dies ebenfalls berücksichtigen.

Bonus

Die meisten Leute werden diese Seite nutzlos finden, wenn sie den schnellsten Algorithmus oben kennen. Bitte lesen Sie das Folgende nur für diejenigen, die den Implementierungsprozess sehen möchten, der zum schnellsten Algorithmus führt.

Einfache Implementierung

Eine Krafttechnik, um zu überprüfen, ob sie tatsächlich teilbar ist, während die zu teilende Zahl durch eins erhöht wird. Ich habe mir diese Methode selbst ausgedacht, aber sie war zu langsam.

private static bool IsPrime(int num)
{
    if (num < 2) return false;

    for (int i = 2; i < num; i++)
    {
        if (num % i == 0)
        {
            //Keine Primzahl
            return false;
        }
    }

    //Ist eine Primzahl
    return true;
}

Eine leicht verbesserte Version der einfachen Implementierung

Mit ein wenig Einfallsreichtum in einer einfachen Implementierung wird die Verarbeitungsgeschwindigkeit halbiert. Einfach ausgedrückt, wir wissen, dass Evens durch 2 teilbar sind. Entfernen wir sie also im Voraus. Ebenso scheint es, dass Vielfache von 3 und 5 im Voraus entfernt werden können, aber es scheint nicht so dramatisch schneller zu sein.

private static bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; //Schließen Sie gerade Zahlen im Voraus aus

    for (int i = 3; i < num; i+=2)
    {
        if (num % i == 0)
        {
            //Keine Primzahl
            return false;
        }
    }

    //Ist eine Primzahl
    return true;
}

Referenzquelle

Prime Judgement-Wikipedia Primzahlurteil|Algorithmus und Datenstruktur| Aizu Online Judge

Schnellstes Primzahl-Beurteilungsprogramm C # Java C ++