Inhalt
Die Fakten:
| Plattform: | codewars.com |
| Name: | Backwards Read Primes |
| Level: | 6 kyu |
| Sprache: | TypeScript |
Beschreibung:
Backwards Read Primes are primes that when read backwards in base 10 (from right to left) are a different prime. (This rules out primes which are palindromes.)
Examples:
13 17 31 37 71 73 are Backwards Read Primes
13 is such because it's prime and read from right to left writes 31 which is prime too. Same for the others.
Task
Find all Backwards Read Primes between two positive given numbers (both inclusive), the second one always being greater than or equal to the first one. The resulting array or the resulting string will be ordered following the natural order of the prime numbers.
Examples (in general form):
backwardsPrime(2, 100) => [13, 17, 31, 37, 71, 73, 79, 97] backwardsPrime(9900, 10000) => [9923, 9931, 9941, 9967] backwardsPrime(501, 599) => []
See "Sample Tests" for your language.
Notes
- Forth Return only the first backwards-read prime between start and end or 0 if you don't find any
- Ruby Don't use Ruby Prime class, it's disabled.
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 macht es Sinn eine Helfer-Funktion zu basteln, die (effektiv) checkt, ob eine Zahl eine Primzahl ist.
Schritt 2
Dazu können wir die Trial-Devision bzw. Probedivision anwenden.
Schritt 3
Dann können wir in unserer Hauptfunktion von start bis stop loopen.
Schritt 4
Wenn die aktuelle Zahl eine Primzahl ist, prüfen wir, ob sie auch rückwärts eine Primzahl ist.
Schritt 5
Außerdem soll es rückwärts nicht die gleiche Zahl wie vorwärts sein.
Schritt 6
Wenn beides zutrifft, fügen wir die Zahl zu einem Array hinzu.
Code
Geil. Übersetzen wir unseren Pseudo-Code in TypeScript:
Lösungsschritte
Die erste Zeile meiner Helfer-Funktion:
function isPrime(num: number): boolean {
Als erstes schließen wir alles aus, was kleiner als 1 ist:
if (num <= 1) return false;
Jetzt loopen wir (effizient) bis zur Wurzel unserer zu prüfenden Zahl:
for (let i = 2; i <= Math.sqrt(num); i++) {
Siehe Trial Division, bzw. Probedivision.
Wenn unsere Zahl durch eine der aktuellen Zahlen teilbar ist, ist es keine Primzahl:
if (num % i === 0) return false;
}
Und wir können den Loop (und die Funktion) mit return sofort beenden.
Ansonsten schon:
return true;
}
Das war unserer Helferlein. Weiter geht's mit der Hauptfunktion.
Die erste Zeile meiner Hauptfunktion:
export function backwardsPrime(start: number, stop: number): number[] {
Ich erstelle mir das Array für die gesammelten Rückwärts-Primzahlen:
const backwardsPrimes: number[] = [];
Jetzt der Loop:
for (let i = start; i <= stop; i++) {
Wir prüfen jede Zahl, ob es eine Primzahl ist:
if (isPrime(i)) {
Dabei hilft uns unser Helferlein von oben.
Wenn es eine Primzahl ist, können wir sie umdrehen:
const revNum = Number([...String(i)].reverse().join(""));
Wir spreaden die Ziffern der String-Zahl in ein Array, das wir dann umdrehen, wieder zusammenfügen und zurück in eine Zahl umwandeln.
Dann prüfen wir, ob die Rückwärts-Zahl auch eine Primzahl und nicht die gleiche Zahl wie vorwärts ist:
if (isPrime(revNum) && revNum !== i) backwardsPrimes.push(i);
}
}
Wenn das passt, fügen wir die Zahl zu unserem Ergebnis-Array hinzu.
Nach dem Loop nur noch das Ergebnis zurückgeben:
return backwardsPrimes;
}
Fertsch! 💪
Komplettlösung
export function backwardsPrime(start: number, stop: number): number[] {
const backwardsPrimes: number[] = [];
for (let i = start; i <= stop; i++) {
if (isPrime(i)) {
const revNum = Number([...String(i)].reverse().join(""));
if (isPrime(revNum) && revNum !== i) backwardsPrimes.push(i);
}
}
return backwardsPrimes;
}
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;
}