Blog

197 wird Ring-Primzahl genannt, da alle ihre Rotationen 971 und 719 ebenfalls Primzahlen sind.

Es gibt 13 solche Zahlen unter 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, und 97.

Wie viele solche Zahlen gibt es unter 1000000?

Lösung

Wir berechnen zunächst die Primzahlen unter 1000000 mit dem Siebverfahren, dann prüfen wir jede Primzahl auf die Ring-Eigenschaft:

clc
clear all
tic

limit = 1000000;

testPrimes = ones(1, limit);
for div = 2 : sqrt(limit)
    for multiple = 2 : (limit / div)
        testPrimes(div * multiple) = 0;
    end
end

realPrimes = ones(1, limit);
counter = 0;
for i = 1 : limit
    if testPrimes(i) == 1
        counter = counter + 1;
        realPrimes(counter) = i;
    end
end

primes = realPrimes(1:counter);
circ = 0;

for i = 1 : counter
    digitCount = 0;
    lengthTest = primes(i);
    while lengthTest > 0
        digitCount = digitCount + 1;
        lengthTest = floor(lengthTest / 10);
    end
    digits = ones(1, digitCount);
    
    for p = 1 : digitCount
        digits(p) = mod(floor(primes(i) / 10^(digitCount - p)), 10);
    end
    
    isCirc = 1;
    for r = 1 : digitCount
        num = 0;
        pot = 0;
        for d = r : r + digitCount - 1
            pos = mod(d, digitCount);
            if pos == 0
                pos = digitCount;
            end
            num = num + digits(pos) * 10^(digitCount - pot - 1);
            pot = pot + 1;
        end
        
        found = 0;
        for t = 1 : counter
            if num == primes(t)
                found = 1;
            end
        end

        if found ~= 1
            isCirc = 0;
        end
    end
    
    if digitCount == 1
        isCirc = 1;
    end
    
    if isCirc == 1
        circ = circ + 1;
    end
end

disp(['circular primes: ' num2str(circ - 1)]);
toc

Ergebnis: 55
Rechenzeit: 430 Sekunden

Die Rechenzeit können wir noch deutlich reduzieren. Zunächst benutzen wir zum berechnen der Primzahlen die Funktion

prim = primes(1e6);

Wir verwenden dann ein binäres Feld, um später logische Operatoren anwenden zu können:

istPrim = false(1e6, 1);
istPrim(prim) = true;

Statt unserer vorherigen Methode zur Bestimmung der Anzahl der Ziffern der aktuellen Zahl benutzen wir den Zehnerlogarithmus:

ziffern = ceil(log10(prim));

Anschließend testen wir jeweils alle Primzahlen mit der gleichen Anzahl an Ziffern gleichzeitig. Der gesamte Code:

clc
clear all
tic

prim = primes(1e6);
prim = prim(:);

stellen = 6;

istPrim = false(1e6, 1);
istPrim(prim) = true;

circPrim = true(size(prim));

prim2 = prim;
ziffern = ceil(log10(prim));

for j = 1 : stellen
    prim2 = floor(prim2/10) + mod(prim2, 10) .* 10 .^ (ziffern-1);
    circPrim = circPrim  & istPrim(prim2);
end

circs = sum(circPrim);

disp(['circular primes: ' num2str(circs)]);
toc

Ergebnis: 55
Rechenzeit: 0.066573 Sekunden