037 – Summe der beidseitig trunkierbare Primzahlen

 

Die Primzahl 3797 hat die interessante Eigenschaft, dass man von beiden Seiten beliebig viele Ziffern entfernen kann und stets wieder eine Primzahl erhält (von links 3797, 797, 97, 7 und von rechts 3797, 379, 37, 3).

Finde die Summe der einzigen elf beidseitig trunkierbaren Primzahlen. Hinweis: 2, 3, 5 und 7 sind hier ausgeschlossen.

Lösung

Hier zunächst die anschauliche Lösung, die alle ungeraden Zahlen auf die gewünschte Eigenschaft testet:

clc
clear all
tic

gefunden = 0;
summe = 0;
test = 11;

while (gefunden < 11)
    if (isprime(test))
        testString = num2str(test);
        ziffern = length(testString);
        gefunden = 1;
        for ziffer = 1 : ziffern
            if (ziffer < ziffern)
                teil = str2double(testString(1 : ziffer));
                if (~isprime(teil))
                    gefunden = 0;
                    break
                end
            end
            if (ziffer > 1)
                teil = str2double(testString(ziffer : ziffern));
                if (~isprime(teil))
                    gefunden = 0;
                    break
                end
            end
        end
        if (gefunden)
            gefunden = gefunden + 1;
            summe = summe + test;
        end
    end
    test = test + 2;
end

summe
toc

Ergebnis: 748317
Rechenzeit: 32.77265 Sekunden

In Matlab ist es immer besser, die zu testenden Zahlen in Matrizen zu schreiben und alle gleichzeitig zu bearbeiten. Eine solche Lösung ist deutlich performanter:

clc
clear all
tic

prim = primes(1e6);

rechtsLinks = prim;
istRechtsLinks = true(1, length(prim));
while (max(rechtsLinks) > 10)
    rechtsLinks = floor(rechtsLinks / 10);
    positiv = (rechtsLinks > 0);
    istRechtsLinks(positiv) = istRechtsLinks(positiv) & ...
        ismember(rechtsLinks(positiv), prim);
end

linksRechts = prim;
istLinksRechts = true(1, length(prim));
while (max(linksRechts) > 10)
    linksRechts = mod(linksRechts, 10.^(floor(log10(linksRechts))));
    positiv = (linksRechts > 0);
    istLinksRechts(positiv) = istLinksRechts(positiv) & ...
        ismember(linksRechts(positiv), prim);
end

disp(sum(prim(istRechtsLinks & istLinksRechts & (prim > 10))));
toc;

Ergebnis: 748317
Rechenzeit: 0.167456 Sekunden

Ähnliche Artikel

Kommentar verfassen