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