Alle Herausforderungen
Mittel 0 gelöst 0% Erfolgsquote

Quadratische Primzahlformeln

Finde den quadratischen Term n² + an + b, der ab n = 0 die längste Folge von Primzahlen liefert.

Das lernst du

  • Mit Probedivision auf Primzahl testen
  • Einen Suchraum mit zwei Parametern durchsuchen
  • Regeln für Gleichstände anwenden

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

Beispiel 1
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].

Beispiel 2
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.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.