p1.c

acm大赛题

/// P1

#include <stdio.h>
#include <stdlib.h>

#define NUMMAX 1000000
#define MAXFACTOR 1000

char isPrime[ NUMMAX];

void prePrime() {
   int i, n;

   isPrime[0] = 0;
   isPrime[1] = 0;
   isPrime[2] = 1;

   for( i = 3; i < NUMMAX; i++) {
      if( i%2 == 0)
         isPrime[i] = 0;
      else
         isPrime[i] = 1;
   }

   for( i = 3; i < MAXFACTOR; i += 2)
      for( n = i+i; n < NUMMAX; n += i)
         isPrime[n] = 0;
}

int digitRoot( int n) {
   int d = 0;

   while( n != 0 ) {
      d += n % 10;
      n /= 10;
   }

   return d;
}

int main(void) {
   int n, m;

   prePrime();

   scanf( "%d", &n);

   while ( n > 0) {
     m = n;

     while( !isPrime[m] && m >= 10)
        m = digitRoot(m);

     if( isPrime[m])
        printf( "%7d %7d\n", n, m);
     else
        printf( "%7d    none\n", n);

     if( scanf( "%d", &n) != 1)
        exit(0);
   }

   return 0;
}