The solution to wonderprimes requires a routine to test prime-ness along with code to process the integer parts of numbers that might qualify as wonderprimes.
Efficiency is generally important for prime-testing routines which require brute-force testing. The factors to be tested to disqualify a prime range from 2 through sqrt(n). Of course, even numbers starting with 4 need not be tested. One set of logic to do this looks like this:
prime (n) { int i; if (n > 0 && n <= 3) return 1; if (n %2 == 0) return 0; for (i = 3; i*i <= n; i+=2) if (n % i == 0) return 0; return 1; }The termination condition of i*i <= n is one way to test only the factors of integer. One could also start at sqrt(n) (as calculated by some math routine) and count backwards. I haven't done the tests to see if that's faster or not since the sqrt() takes a while to compute and most numbers are quickly disqualified with low factors.
Disassembling an integer into two pieces requires using the mod (%) and integer divide (/) operators and a power of ten. By way of example, consider the integer 1234567. Here is a table of some powers of ten and the result of mod and integer divide:
Power Divide Mod 10 123456 7 100 12345 67 1000 1234 567 10000 123 4567 100000 12 34567 1000000 1 234567You can see that the operations extract the digits of interest for a wonderprime. Thus candidate/power is the first digits of a candidate wonderprime while candidate%power is the final digits. It might also be clear that one can count the digits of a number by successively dividing by 10 until the number becomes 0.
Another brute force problem, basically the steps are:
Richard Peng's code:
#include <stdio.h> int d,n,ans; int power[10]={1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000}; ndigits (int a) { int ans; for (ans=0; a!=0; a=a/10, ans++); return ans; } void testwonderprime (long pow) { long n1 = n; /* work copy of n */ /**** get bottom digits right ****/ if( (!prime(n1/pow)) || ndigits(n1/pow)<d) /* top digits not prime? */ n1 -= (n1%pow) + pow/10; /* start over on bottom */ for ( ; !(prime(n1%pow)) || ndigits(n1%pow)<d; n1++) ; /* increment bottom digits until prime & long enough */ /**** get top digits right ****/ if (ndigits (n1/pow)<d) /* get enough digits on top */ n1 = n1%pow + power[d-1]*pow; for(; !prime(n1/pow); n1+=pow) /* make top prime */ if (n1 > 2000000000 || n1 < 0) return; if (n1 < 0) return; if (n1 < ans) ans=n1; } main() { long i; FILE *fin=fopen("wpb.in","r"); FILE *fout=fopen("wpb.out","w"); fscanf(fin,"%d %d", &d, &n); ans = 2000000000; /* "infinity" */ for(i=d; i<9; i++) testwonderprime (power[i]); fprintf (fout,"%d\n",ans); fclose (fin); fclose (fout); }