Inhalt
Die Fakten:
| Plattform: | codewars.com |
| Name: | Primorial Of a Number |
| Level: | 6 kyu |
| Sprache: | TypeScript |
Beschreibung:
Definition (Primorial Of a Number)
Is similar to factorial of a number, In primorial, not all the natural numbers get multiplied, only prime numbers are multiplied to calculate the primorial of a number. It's denoted with P# and it is the product of the first n prime numbers.
Task
Given a number N , calculate its primorial.
Notes
- Only positive numbers will be passed (N > 0) .
Input >> Output Examples:
1- numPrimorial (3) ==> return (30)
1 - num_primorial(3, 30).
1 - num_primorial(3) // 30
1 - (num-primorial 3) ;; 30
Explanation:
Since the passed number is (3) ,Then the primorial should obtained by multiplying 2 * 3 * 5 = 30 .
Mathematically written as , P3# = 30 .
2- numPrimorial (5) ==> return (2310)
2 - num_primorial(5, 2310).
2 - num_primorial(5) // 2310
2 - (num-primorial 5) ;; 2310
Explanation:
Since the passed number is (5) ,Then the primorial should obtained by multiplying 2 * 3 * 5 * 7 * 11 = 2310 .
Mathematically written as , P5# = 2310 .
3- numPrimorial (6) ==> return (30030)
3 - num_primorial(6, 30030).
3 - num_primorial(6) // 30030
3 - (num-primorial 6) ;; 30030
Explanation:
Since the passed number is (6) ,Then the primorial should obtained by multiplying 2 * 3 * 5 * 7 * 11 * 13 = 30030 .
Mathematically written as , P6# = 30030 .
Playing With Lists/Arrays Series
Quelle: codewars.com
Lösung
Pseudo-Code
Wie immer gibt's reichlich Varianten, hier ist eine meiner.
Erst die Lösungsschritte in Pseudo-Code. Los geht’s:
Lösungsschritte
Schritt 1
Als Erstes sollten wir uns Gedanken um das Prüfen auf eine Primzahl machen, dazu wäre es sinnvoll, die Primzahl-Prüflogik in eine gesonderte Hilfs-Funktion auszulagern.
Schritt 2
Dafür brauchen wir einen Loop, der von 2 bis zur zu prüfenden Zahl loopt und in jedem Loop prüft, ob unsere potentielle Primzahl durch die aktuelle Zahl teilbar ist.
Schritt 3
Außerdem sollte sie möglichst effizient sein, wir können zum Beispiel die "Trial Division" (zu deutsch: "Probedivision") verwenden.
Schritt 4
Wenn wir unsere Prim-Prüf-Hilfsfunktion haben, können wir uns wieder der numPrimorial widmen.
Schritt 5
Auch hier können wir wieder einen Loop verwenden.
Schritt 6
Wenn die aktuelle Zahl eine Primzahl ist, multiplizieren wir sie einfach zu einer Produkt-Variablen hinzu.
Schritt 7
Das müssen wir solange machen bis n erreicht ist.
Code
Geil. Übersetzen wir unseren Pseudo-Code in TypeScript:
Lösungsschritte
Die erste Zeile meiner Prim-Prüf-Hilfsfunktion:
function isPrime(num: number): boolean {
Primzahlen sind nur durch 1 und sich selbst teilbar. Darum können wir erst mal alle Zahlen ausschließen, die kleiner oder gleich 1 sind:
if (num <= 1) return false;
Jetzt der Loop:
for (let i = 2; i <= Math.sqrt(num); i++) {
Wir legen bei 2 los, weil: siehe oben.
Dann der Clou: Wir loopen nicht bis zu unserer zu prüfenden Zahl, sondern nur bis zu ihrer Wurzel. Wem et interessiert, hier steht mehr dazu.
Jetzt prüfen wir für jede Zahl (ab 2), ob sie unsere potentielle Primzahl teilen kann:
if (num % i === 0) return false;
}
Wenn ja, ist unsere potentielle Primzahl keine Primzahl und wir können mit einem false abbrechen.
Ansonsten:
return true;
}
Gibts ein wunderbares true zurück! Ende der Prim-Prüf-Hilfsfunktion.
Jetzt die erste Zeile meiner Hauptfunktion:
export function numPrimorial(n: number): number {
Auch hier ein Loop:
for (let i = 0; i < n; ) {
Das i++ lasse ich hier weg, da ich mein i abhängig von einer Bedingung erhöhen möchte.
Hier die Bedingung:
if (isPrime(num)) {
Hier kommt unsere Primzahl-Prüf-Hilfsfunktion zum Einsatz. num müssen wir oben noch initialisieren. In meinem Fall so: let num = 1
Wenn wir eine Primzahl haben, multiplizieren wir sie zu einer Ergebnis-Variablen:
output *= num;
Auch unseren output müssen wir oben initialisieren: let output = 1. Damit sieht unser Funktions-Kopf etwa so aus:
export function numPrimorial(n: number): number {
let output = 1;
let num = 1;
...
Außerdem erhöhen wir bei einer gefundenen Primzahl unser i:
i++;
}
Wir wollen ja solange loopen, bis wir n Primzahlen gefunden haben.
Weiter geht’s nach der if-Bedingung:
num++;
}
Ob Primzahl oder nicht. In jedem Fall wollen wir die nächste Zahl prüfen. Darum erhöhen wir nach der if-Bedingung unser num um 1:
Nach der For-Schleife geben wir unser Ergebnis zurück:
return output;
}
Voilá! 💪
Komplettlösung
export function numPrimorial(n: number): number {
let output = 1;
let num = 1;
for (let i = 0; i < n; ) {
if (isPrime(num)) {
output *= num;
i++;
}
num++;
}
return output;
}
function isPrime(num: number): boolean {
if (num <= 1) return false;
for (let i = 2; i <= Math.sqrt(num); i++) {
if (num % i === 0) return false;
}
return true;
}