[UVA967]Circular

題目敘述

A circular prime is a prime number that remains prime as each leftmost digit (most significant digit), in turn, is moved to the right hand side. For instance, the number 19937 is a circular prime, since all numbers in the sequence 19937, 99371, 93719, 37199 and 71993 are prime numbers.

Your objective is to write a program that, given a range, computes the number of circular primes in that range. Input The input consists of a sequence of pairs of integers i and j, with one pair of integers per input line. All integers will be less than 1,000,000 and greater or equal to 100. You can assume that in any pair i is lesser or equal than j.

You should process all pairs of integers, and for each such pair, count the number of circular primes between i and j, including i and j. Input is terminated by a line just with the number ‘-1’. Output For each pair of input integers, defining a range, the output should be: ‘No Circular Primes.’ (if there are no circular primes in the range), ‘1 Circular Prime.’ (if only one circular prime exists in the range), or ‘n Circular Primes.’ (if there are n circular primes in the range, and n is greater than one).

想法

先建好Circular表，然後再去做比對。因為質數的性質(一個合數n一定可以拆成一個小於根號n的 * 一個大於根號n的)，所以1000000只要找1000內是否有它的因數即可。而且只需要判斷是否是質數的倍數即可(線性篩法)，做完再用字串去做DP。

作法參考: A - CIRCULAR

#include <stdio.h>
#include <string.h>
#include <math.h> 
#define max 1000000 
int dp[1000001] = {0}; 
int prime[1001] = {0}; 
bool mark[1001] = {0}; 
int num = 0; 
void sieve() { 
  mark[0] = mark[1] = 1; 
  for(int i = 2 ; i < 1000 ; ++i) { 
    if(!mark[i]) { 
      prime[num++] = i; 
      for(int j = 2 ; i * j < 1000 ; ++j) { 
        mark[i * j] = 1; 
        } 
      } 
    } 
    /* 
    for(int i = 0 ; i < num ; ++i) { 
      printf("%d\n",primei); 
    } 
    */ 
  } 
bool judge_prime(int n) { 
  for(int i = 0 ; prime[i] < sqrt(n) && i < num ; ++i ) { 
    if(!(n % prime[i])) return 0; 
  } 
  return 1; 
} 
void bulid_dp() { 
  for(int i = 100 ; i <= 1000000 ; ++i) { 
    char str[8]; 
    dp[i] += dp[i-1]; 
    sprintf(str,"%d",i); 
    int len = strlen(str); 
    int n,temp; 
    for(int j = 0 ; j <= len ; ++j) { 
      sscanf(str,"%d",&n); 
      if(judge_prime(n) == 0) break; 
      temp = str[0]; 
      for(int k = 1 ; k < len ; ++k) { 
        str[k-1] = str[k]; 
      } 
      strle[n-1] = temp; 
      if(j == len) { 
        dp[i++]; break; 
      } 
    } 
  } 
} 
int main() { 
  sieve(); 
  bulid_dp(); 
  int a,b; 
  while(scanf("%d", &a) && a != -1) { 
    scanf("%d",&b); 
    int ans = dp[b]- dp[a]; 
    if(ans == 0 ) printf("No Circular Primes.\\n"); 
    else if(ans == 1) printf("1 Circular Prime.\\n"); 
    else printf("%d Circular Primes.\\n",ans); 
  } 
  return 0; 
}