USACO DEC06 Problem 'wpb' Analysis

by Rob Kolstad

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    234567
You 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);
}