050 – Summe aus fortlaufenden Primzahlen

 

Die Primzahl 41 kann als die Summe aus sechs fortlaufenden Primzahlen geschrieben werden:

41 = 2 + 3 + 5 + 7 + 11 + 13

Das ist die größte Anzahl an fortlaufenden Primzahlen, deren Summe unter 100 liegt.

Die größte Anzahl an fortlaufenden Primzahlen unter 1000, deren Summe unter 1000 liegt, ist 953 (21 Terme).

Welche Primzahl unter 1000000 kann als die Summe der meisten fortlaufenden Primzahlen geschrieben werden?

Lösung

In guter Matlab-Manier schreiben wir zunächst die Primzahlen unter 1000000 in einen Vektor und erstellen einen weiteren Vektor mit der kummulativen Summe. Anschließend erstellen wir eine große Matrix mit den Primzahlen auf der Diagonalen und den kummulativen Summen in der oberen rechten Dreiecksmatrix. Die linke untere Dreiecksmatrix ist leer. 21 Terme gilt es zu schlagen. Wir wissen also, dass die erste der fortlaufenden Primzahlen kleiner als 47619 = 1000000 / 21 sein muss. Dadurch können wir die Matrix klein genug für den Speicher halten.

Nun suchen wir die Zeilen- und Spaltenindizes der Elemente der Matrix, die selbst Primzahlen sind. Die Summe mit den meisten Termen ist das Element der Matrix mit der größten horizontalen Entfernung von der Diagonalen, also max(colIdx – rowIdx + 1).

clc
clear all
tic

grenze = 1e6;
x = primes(grenze);
y = cumsum(x);

maxSummanden = find(y > grenze, 1);
maxStart = 47619;
maxStartIdx = find(x < maxStart, 1, 'last');
z = repmat(y(1 : maxStartIdx), maxSummanden, 1) ...
    - repmat([0; y(1 : (maxSummanden - 1))'], 1, maxStartIdx);
z(z < 0) = 0;
z(z > grenze) = 0;

w = reshape(ismember(z, x), maxSummanden, maxStartIdx);
[x1, y1] = find(w);
longestRun = max(y1 - x1 + 1);
w2 = [x1, y1, y1 - x1 + 1];
maxIdx = find(w2(:, 3) == longestRun);
z(w2(maxIdx, 1), w2(maxIdx, 2))

toc

Ergebnis: 997651
Rechenzeit: 0.174670 Sekunden

Ähnliche Artikel

Kommentar verfassen