Örneğin, 200=5223 ya da 120072949=232613.
İlk beş sqube sayıları şunlardır: 72, 108, 200, 392 ve 500.
Ayrıca ilginçtir ki, 200 sayısı herhangi bir basamağı değiştirilerek asal sayıya dönüştürülemeyen ilk sayıdır; böyle sayılara "asal-korumalı" adı verilir. Bir sonraki "200" sayısını içinde barındıran asal-korumalı sqube sayısı 1992008 dir.
"200" sayısını içinde barındıran 200. asal-korumalı sqube sayısını bulunuz.
Cevap: 229161792008.
Örnek algoritmalar: C/C++
void Euler200() {
long LIMIT = 1000000000000L;
int[] pr = getPrimeList(1000000);
ArrayList<Long> nums = new ArrayList<Long>();
for (int i=0; i<pr.length; i++) {
long p = pr[i];
long pp = p*p;
for (int j=0; j<pr.length; j++) {
long ppqqq = pp;
long q = pr[j];
ppqqq = ppqqq*q; if (ppqqq > LIMIT) break;
ppqqq = ppqqq*q; if (ppqqq > LIMIT) break;
ppqqq = ppqqq*q; if (ppqqq > LIMIT) break;
nums.add(ppqqq);
}
}
ArrayList<Long> res = new ArrayList<Long>();
for (long x: nums) {
String s = String.valueOf(x);
if (s.indexOf("200") != -1 && isPrimeProof(x)) {
res.add(x);
}
}
Collections.sort(res);
System.out.println("Ans=" + res.get(199));
}
boolean isPrimeProof(long x) {
String s = String.valueOf(x);
for (int i=0; i<s.length(); i++) {
char dig = s.charAt(i);
for (char c='0'; c<='9'; c++) if (c!=dig) {
String t = s.substring(0, i) + c + s.substring(i+1);
BigInteger T = new BigInteger(t);
if (T.isProbablePrime(100)) {
return false;
}
}
}
return true;
}
int[] getPrimeList(int n) {
int[] p = new int[n];
int np = 0;
for (int i=2; np < n; i++) {
boolean ok = true;
for (int j=0; j<np && p[j]*p[j]<=i; j++) {
if (i%p[j] == 0) {
ok = false;
break;
}
}
if (ok) p[np++] = i;
}
return p;
}
public static void main(String[] args) {
final long time = -System.currentTimeMillis();
final Collection<BigInteger> biPrimes = new ArrayList<BigInteger>();
for (long p = 2; p < 3000000; p++) {
if (millerRabin(p)) {
biPrimes.add(BigInteger.valueOf(p));
}
}
final BigInteger[] primes = biPrimes.toArray(new BigInteger[biPrimes.size()]);
final Collection<Long> colSqubes = new ArrayList<Long>();
for (final BigInteger p : primes) {
if (p.pow(2).toString().length() <= 16) {
for (final BigInteger q : primes) {
if (!p.equals(q)) {
final BigInteger sqube = p.pow(2).multiply(q.pow(3));
if (sqube.toString().length() <= 16) {
if (sqube.toString().contains("200")) {
colSqubes.add(sqube.longValue());
}
} else {
break;
}
}
}
}
}
final Long[] squbes = colSqubes.toArray(new Long[colSqubes.size()]);
Arrays.sort(squbes);
int count = 0;
for (final Long sqube : squbes) {
final char[] chars = sqube.toString().toCharArray();
boolean isPrime = false;
for (int i = 0; ((i < chars.length) && (!isPrime)); i++) {
final char[] nchars = chars.clone();
for (char c = '0'; ((c <= '9') && (!isPrime)); c++) {
if ((chars[i] != c) && ((i != 0) || (c != '0'))) {
nchars[i] = c;
final long n = Long.parseLong(new String(nchars));
if (millerRabin(n)) {
isPrime = true;
}
}
}
}
if (!isPrime) {
count++;
if (count == 200) {
System.out.println("The 200th number is " + sqube + ", found in " + ((time + System.currentTimeMillis()) / 1000) + "s.");
System.exit(0);
}
}
}
}
private static boolean millerRabinPass(final int a, final long n) {
long d = n - 1;
final long s = Long.numberOfTrailingZeros(d);
d >>= s;
long aToPower = modularExponent(a, d, n);
if (aToPower == 1) {
return true;
}
for (int i = 0; i < s-1; i++) {
if (aToPower == n-1) {
return true;
}
aToPower = modularExponent(aToPower, 2, n);
}
if (aToPower == n-1) {
return true;
}
return false;
}
public static boolean millerRabin(final long n) {
if (n <= 1) {
return false;
} else if (n == 2) {
return true;
} else if (
(millerRabinPass(2, n)) &&
((n <= 7) || (millerRabinPass( 7, n))) &&
((n <= 61) || (millerRabinPass(61, n)))
) {
return true;
} else {
return false;
}
}
private static long modularExponent(final long base, final long power, final long modulus) {
return BigInteger.valueOf(base).modPow(BigInteger.valueOf(power),
BigInteger.valueOf(modulus)).longValue();
} > with(ListTools):
> decompt:=proc(n)
> local t,N;
> t:=NULL; N:=n;
> while N<>0 do
> t:=t,N mod 10;
> N:=iquo(N,10)
> od;
> Reverse([t]);
> end:
>
> recompt:=proc(t)
> local n,i;
> n:=0;
> for i in t do
> n:=n*10+i
> od;
> n;
> end:
>
> isprimeproof:=proc(n)
> local a,i,y,N,j,t;
> t:=decompt(n); N:=nops(t);
> for i from 1 to N do
> y:=t;
> for j from 0 to 9 do
> y[i]:=j;
> if isprime(recompt(y)) then return false fi
> od;
> od;
> true;
> end:
>
> iscontaining200:=proc(n)
> local N;
> N:=n;
> while N>100 do
> if N mod 1000=200 then return true fi;
> N:=iquo(N,10)
> od;
> false;
> end:
>
> t:=time(): L:=NULL: k:=0:
> for a from 1 to 1000 do
> k:=nextprime(k);
> n:=0: r:=0:
> while r<10^12 do
> n:=nextprime(n);
> r:=n^2*k^3;
> if isprimeproof(r) and iscontaining200(r) then L:=L,r fi
> od:
> od:
> sort([L])[200]; time()-t; z = {};
Do[
Do[
If[a != b,
s = Prime[a]^2*Prime[b]^3;
If[s > 1000000000000,
Break[];
];
If[StringMatchQ[ToString[s], "*200*"],
m = IntegerDigits[s];
For[i = 1, i <= Length[m], i++,
q = m;
Do[
q[[i]] = x;
If[PrimeQ[FromDigits[q]],
Goto[Here];
];
,
{x, 0, 9}
];
];
z = Append[z, s];
];
Label[Here];
];
,
{a, 1, 100000}
];
,
{b, 1, 10000}
];
Print[Sort[z][[200]]];