1015 reversible primes (20 points)

1015 Reversible Primes (20 branch )

The question

Give two integers at a time ,N,D, Ask for judgment N and N stay D Are all prime numbers after base down flip .

Ideas

The prime sieve judges prime numbers , Right again N stay D Base down flip . First judge N Is it a prime , Then judge whether the inverted number is a prime number , Be careful 0 and 1 Not prime .

Code

#include<stdio.h>
#include<string.h>

int prime[1000000];
bool number[1000000];

void Prime(int n)
{
	int count=0;
	memset(number,0,sizeof(number));
	number[1]=1;
	number[0]=1;
	for(int i=2; i<=n; i++){
		if(!number[i]){
			prime[count++]=i;
		}
		for(int j=0;j<count&&i*prime[j]<=n;j++){
			number[i*prime[j]]=1;
			if(i%prime[j]==0){
				break;
			}
		}
	}
}

int reverse(int N,int D)
{
	int x[100],cnt=0,sum=0,weight=1;
	while(N){
		x[cnt++]=N%D;
		N/=D;
	}
	for(int i=cnt-1; i>=0; i--){
		sum+=x[i]*weight;
		weight*=D;
	}
	return sum;
}

int main()
{
	int N,D,x;
	Prime(100007);
	while(scanf("%d",&N)){
		if(N<0){
			break;
		}
		scanf("%d",&D);
		if(!number[N]){
			x=reverse(N,D);
			if(!number[x]){
				printf("Yes\n");
			}else{
				printf("No\n");
			}
		}else{
			printf("No\n");
		}
	}
	return 0;
}