Inhalt
Die Fakten:
| Plattform: | codewars.com |
| Name: | The search for Primes! Twin Primes! |
| Level: | 6 kyu |
| Sprache: | TypeScript |
Beschreibung:
A twin prime is a prime number that is either 2 less or 2 more than another prime number—for example, either member of the twin prime pair (41, 43). In other words, a twin prime is a prime that has a prime gap of two. Sometimes the term twin prime is used for a pair of twin primes; an alternative name for this is prime twin or prime pair. (from wiki https://en.wikipedia.org/wiki/Twin_prime)
Your mission, should you choose to accept it, is to write a function that counts the number of sets of twin primes from 1 to n.
If n is wrapped by twin primes (n-1 == prime && n+1 == prime) then that should also count even though n+1 is outside the range.
Ex n = 10
Twin Primes are (3,5) (5,7) so your function should return 2!
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 basteln wir uns eine (effektive) Hilfsfunktion, die testet, ob eine gegebene Zahl eine Primzahl ist.
Schritt 2
In dieser Hilfsfunktion loopen wir durch die Zahlen von 21 bis zu ihr selbst und testen, ob sie unsere zu testende Primzahl sauber teilen kann.
TIPPHier gibt es einen kleinen Trick. Wir müssen nicht unbedingt bis zur Zahl selbst loopen... 😉
Weiter geht’s mit der Hauptfunktion.
Schritt 3
In unserer Hauptfunktion brauchen wir als Erstes einen Counter um die gefundenen Twin-Primes zu zählen.
Schritt 4
Dann loopen wir durch die Zahlen von 1 (bzw. 2)1 bis n.
Schritt 5
Jetzt testen wir die aktuelle Zahl, ob sie eine Primzahl ist.
Schritt 6
Wenn ja, testen wir auch die übernächste Zahl, ob sie eine Primzahl ist.
Schritt 7
Wenn beides zutrifft, können wir unseren Zähler um 1 erhöhen und zur nächsten Iteration übergehen.
Schritt 8
Nach dem Loop geben wir nur noch den Inhalt unseres Zählers zurück.
Code
Geil. Übersetzen wir unseren Pseudo-Code in TypeScript:
Lösungsschritte
Die erste Zeile meiner Hilfsfunktion:
function isPrime(n: number): boolean {
Dann direkt der Loop:
for (let i = 2; i <= Math.sqrt(n); i++) {
Wir starten den Loop erst bei 21.
Und um das Ganze effektiver zu machen, loopen wir nur bis zur Wurzel der aktuellen Zahl. Wenn die Zahl bis hierhin nicht sauber teilbar war, ist sie es danach auch nicht mehr.
Dann prüfen wir, ob die aktuelle Zahl n durch das aktuelle i teilbar ist:
if (n % i === 0) return false;
}
Wenn ja, ist es keine Primzahl. Wir können den Loop und die Funktion sofort beenden und false zurückgeben.
Das war's schon für den Loop.
Ansonsten geben wir nach dem Loop true zurück:
return true;
}
Und das war's auch schon für die Hilfsfunktion. Weiter geht’s mit der Hauptfunktion.
Die erste Zeile meiner Hauptfunktion:
export function twinPrime(n: number): number {
Dann unseren Zähler initialisieren:
let numTwinPrimes = 0;
Danach direkt der Loop durch die Zahlen von 2 bis n:
for (let i = 2; i < n; i++) {
Auch hier starten wir den Loop wieder erst ab der 2.
Außerdem brauchen wir nur bis einschließlich n-1 loopen. Warum wird im nächsten Schritt klar.
Jetzt testen wir, ob die aktuelle und die übernächste Zahl Primzahlen sind:
if (isPrime(i) && isPrime(i + 2)) numTwinPrimes++;
}
Wenn ja, erhöhen wir unseren Zähler um 1.
Und das war's schon für den Loop!
Nach dem Loop nur noch den Inhalt des Zählers zurückgeben:
return numTwinPrimes;
}
Voilá! 💪
Komplettlösung
export function twinPrime(n: number): number {
let numTwinPrimes = 0;
for (let i = 2; i < n; i++) {
if (isPrime(i) && isPrime(i + 2)) numTwinPrimes++;
}
return numTwinPrimes;
}
function isPrime(n: number): boolean {
for (let i = 2; i <= Math.sqrt(n); i++) {
if (n % i === 0) return false;
}
return true;
}