Problem
Manche quadratischen Terme liefern erstaunlich viele Primzahlen. n² + n + 41 ergibt für n = 0 bis 39 lauter Primzahlen. Zähle für ganze Zahlen a und b mit |a| ≤ limit und |b| ≤ limit, für wie viele aufeinanderfolgende Werte n = 0, 1, 2, ... der Term n² + an + b eine Primzahl ist. Beim ersten Wert, der keine Primzahl ist, hörst du auf. Finde das Paar mit der längsten Folge.
Implementiere quadratic_primes(limit).
Eingabe
limit: Die Schranke für die Beträge von a und b.
Ausgabe
Gib [a, b, run] zurück, wobei run die Anzahl der Primzahlen in der längsten Folge ist. Bei Gleichstand nimm das kleinste a und danach das kleinste b. Zahlen unter 2 sind keine Primzahlen, ein Paar, dessen Wert bei n = 0 keine Primzahl ist, hat also eine Folge der Länge 0.
Einschränkungen
0 ≤ limit ≤ 300
Beispiele
Eingabe:
limit = 3
Erwartete Ausgabe:
expected = [-2, 3, 3]
Eingabe:
long long limit = 3;
Erwartete Ausgabe:
std::vector<long long> expected = {-2, 3, 3};
Eingabe:
long limit = 3;
Erwartete Ausgabe:
long[] expected = new long[] {-2, 3, 3};
Erläuterung
Mit a = −2 und b = 3 lauten die Werte für n = 0, 1, 2, 3 der Reihe nach 3, 2, 3, 6, das sind drei Primzahlen. Kein Paar ist besser und kein kleineres a kommt gleich, also lautet die Antwort [-2, 3, 3].
Eingabe:
limit = 1
Erwartete Ausgabe:
expected = [-1, -1, 0]
Eingabe:
long long limit = 1;
Erwartete Ausgabe:
std::vector<long long> expected = {-1, -1, 0};
Eingabe:
long limit = 1;
Erwartete Ausgabe:
long[] expected = new long[] {-1, -1, 0};
Erläuterung
b ist −1, 0 oder 1, und keine dieser Zahlen ist prim. Jede Folge hat also die Länge 0, und das kleinste Paar gewinnt: [-1, -1, 0].
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Bei n = 0 ist der Wert gleich b, also muss b prim sein, damit es überhaupt eine Folge gibt.
Hinweis 2
Zähle n hoch, bis der Wert keine Primzahl mehr ist. Negative Werte und Werte unter 2 beenden die Folge.
Hinweis 3
Durchlaufe a und b aufsteigend und ersetze das beste Paar nur bei einer echt längeren Folge.
Erwartete Komplexität
Zeit O(limit² × run × √V), zusätzlicher Speicher O(1)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.