Knowledge base

Primzahlen sind alle natürlichen Zahlen, die nur durch 1 und sich selbst teilbar sind. Die 2 ist Primzahl, sie ist die kleinste und die einzige gerade Primzahl. 

In der Regel wie oben beschrieben ist eine Primzahl nur durch 1 teilbar und sich selbst teilbar. Da es zwei verschiedene Teiler handeln muss scheidet 1 als Primzahl aus.

Das Wort "prim" wurde abgeleitete von Wort "primus" und heisst "Erster, Vorderster". Schon die alten Griechen hatten eine gewisse faszination zu den Primzahlen und entdeckte einige ihrer Eigenschaften.

Heutzutage sind Primzahlen vor allem in der Kryptografie wichtig da der Wert im Zusammenhang mit Primzahlen nicht schnell berechnet werden kann..

Ich habe schon einige Funktionen zum prüfen von Primzahlen in verschiedenen Sprachen gesehen. Was für mich neu war, wie man eine Primzahl auf einem MS-SQL Server berechnet, d.h. mit T-SQL Language. Mit etwas ausprobieren habe ich eine performante Variante für mich gefunden. Die Aufgabe bestand darin Primzahlen von  300300 bis 300900 innerhalb von 30 Sekunden zu berechnen. Meine gefunden Variante schaffte es bei 8 vCPU und 8GB RAM in 15 Sekunden.

MS SQL Transact-SQL FUNCTION

Die Basisfunktion ermittelt von jeweils einer einzelnen Zahl ob sie eine Primzahl ist und gibt jeweils den Rückgabewert (1=WAHR) oder (0=FALSCH). Dabei iterieren man von der Zahl 2 bis zur entsprechenden Wurzel der Zahl.

Die Wurzel basiert auf der Defintion, dass SQRT(n) * SQRT(n) = n ist, und dass mindestens ein Faktor kleiner als gleich SQRT(n) sein muss. Wenn wir keinen Faktor im Bereich 2te, sqrt(n) finden können, bedeutet dies, dass die Zahl n eine Primzahl ist.

Dazu können wir vorher Prüfen ob eine Zahl Gerade oder Ungerade ist. Einzig die 2 ist eine Gerade Primzahl. (Siehe MySQL Version)

IF object_id(N'isPrimeNumber', N'FN') IS NOT NULL
    DROP FUNCTION isPrimeNumber
GO

Create function isPrimeNumber (@number int) 
returns int  as 
Begin
	Declare @result bit = 1,@i int = 2
	
    While (@i<=SQRT(@number))
	Begin
		if(@number % @i = 0)
		Begin
			Set @result = 0
			break
		End
		Set @i += 1
	End
	return @result
End

Der einzelne Aufruf ergibt 0 (NEIN) oder 1 (JA, es ist eine Primzahl) als Resultat.

SELECT dbo.isPrimeNumber(3) AS result

Der Loop

Mittels einer Schleife wird nun die geprüft ob die Zahl eine Primzahl ist. Dabei gibt es nur einen Output wenn die Rückgabe eine 1 ist, d.h. ja, es ist eine Primzahl.

DECLARE @counter INT 
DECLARE @result  INT

SET @counter=300300
WHILE ( @counter <= 300900)
BEGIN
	SET @result = (SELECT dbo.isPrimeNumber(@counter))
	if(@result = 1)
	Begin
		PRINT 'The Number [' + CONVERT(VARCHAR,@counter)+ '] is Prime Number--->'+CONVERT(VARCHAR,@result)
    END
	SET @counter  = @counter  + 1
END

Das Resultat

...
The Number [300857] is Prime Number--->1
The Number [300869] is Prime Number--->1
The Number [300877] is Prime Number--->1
The Number [300889] is Prime Number--->1
The Number [300893] is Prime Number--->1

Completion time: 2024-02-03T23:00:12.5367311+01:00

Die MySQL Variante

Für MySQL oder MariaDB kann man keinen WHILE Schleife direkt durchführen. So muss man wiederum eine Funktion erstellen und diese via einer Prozedur ausführen:

DELIMITER //

CREATE FUNCTION isPrimeNumber ( number INT )
RETURNS INT

BEGIN
   DECLARE result INT;
   DECLARE i INT;
   SET result = 1;
   SET i = 2;
   IF number = 2 THEN
   		Set result = 1;
   ELSEIF number % 2 <> 0 THEN
  
   loop1: WHILE i <= SQRT(number) DO
     IF number % i = 0 THEN
			Set result = 0;
			LEAVE loop1;
	 END IF;
     SET i = i + 1;
   END WHILE loop1;

ELSE
	Set result = 0;
END IF;

   RETURN result;
END; //
DELIMITER ;

Die Prozedur gibt jeweils die Primzahlen aus:

Delimiter //
CREATE PROCEDURE PrimeLoop( start INT, stop INT)
   BEGIN
   DECLARE counter INT default 1;
   DECLARE res VARCHAR(50) default '';
   DECLARE r1 VARCHAR(50) default '';
   WHILE counter <=stop DO
   SET p0=counter; 
   SET r1 = (SELECT `isPrimeNumber`(p0) AS `isPrimeNumber`); 
   IF r1=1 AND counter > 1 THEN
		SELECT CONCAT('N:',counter,' --->',r1,' -->', NOW()) as result;
   END IF;
   
   SET counter = counter + 1;
   
   END WHILE;
   
END //