首页 > 试题广场 >

Reversible Primes (20)

[编程题]Reversible Primes (20)

热度指数：3174 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

A reversible prime in any number system is a prime whose "reverse" in that number system is also a prime. For example in the decimal system 73 is a reversible prime because its reverse 37 is also a prime.

Now given any two positive integers N (< 10⁵ ) and D (1 < D <= 10), you are supposed to tell if N is a reversible prime with radix D.

输入描述:

The input file consists of several test cases.  Each case occupies a line which contains two integers N and D.  The input is finished by a negative N.

输出描述:

For each test case, print in one line "Yes" if N is a reversible prime with radix D, or "No" if not.

示例1

输入

73 10<br/>23 2<br/>23 10<br/>-2

输出

Yes<br/>Yes<br/>No

算法知识视频讲解

donreen

//题目理解了就好做了，以d位基就是要先把n转为d进制的，在d进制的基础上进行逆序，最后判断素数就行了

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <math.h>
#include <vector>
#include <map>
#include <queue>

using namespace std;

bool isPrime (int n) {
    if( n <= 1)
        return false;
    int sqr = (int) sqrt (1.0 * n);
    for(int i = 2; i <= sqr; i++) {
        if( n % i == 0)
            return false;
    }

    return true;
}

int toReverse(int n, int radix){
    vector<int> temp;
    while(n>0){
        temp.push_back(n%radix);
        n = n/radix;
    }

    int result = 0;
    int len = temp.size();
    for(int i=0;i<len;i++){
        result += pow(radix,len-i-1) * temp[i];
    }
    return result;
}

int main() {
    int n,d;
    while(scanf("%d %d", &n, &d)) {
        if(n<0) {
            break;
        }

        int num = n;
        int reverse_num = toReverse(n,d);
        //cout<<num<<" "<<reverse_num<<" ";

        if(isPrime(num) && isPrime(reverse_num) ){
            printf("Yes\n");
        }else{
            printf("No\n");
        }
    }
}

发表于 2019-08-24 17:15:51 回复(0)

C/C++

Myhui

#include <iostream>
using namespace std;
bool isprime(int n){             //判断是否为素数
    if(n<=1) return false;
    for(int i=2;i<n;i++){
        if(n%i==0) return false;
    }
    return true;
}
int reverse(int n,int radix){      //反转数字
    int s[20],num=0,r=1,ans=0;     
    while(n!=0){                  //先化为radix进制
        s[num++]=n%radix;
        n/=radix;
    }
    for(int i=num-1;i>=0;i--){   //反转后再化回十进制
        ans+=s[i]*r;
        r*=radix;
    }
    return ans;
}
int main(){
    int n,d;
    while(1){
        cin>>n;
        if(n<0) break;          //输入负数立即退出循环
        cin>>d;
        if(isprime(n) && isprime(reverse(n,d))) //本身与反转数同时为素数
            cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

编辑于 2018-02-20 21:39:20 回复(0)

C/C++

德芙纵享丝滑

题目不好理解，其实就是：输出数字numA，把numA转换成base进制下的数字numB，再将其反转得到numC，再判断数字numC是否为素数（这个时候将numC视为十进制），如果numA和numC都是素数，则输出Yes，否则输出No；

#include <iostream>
#include<string>
#include <vector>
#include <map>
#include<math.h>
using namespace std;
bool isPrimer(int x)
{
	bool sta = true;
	if (x == 1)
		sta = false;
	else if (x == 2)
		sta = true;
	else
	{
		for (int i = 2; i <= sqrt(x); i++)
			if (x%i == 0)
			{
				sta = false;
				break;
			}	
	}
	return sta;
}
long numreverse(int num, int base)
{
	vector<int> data;
	while (num)
	{
		data.push_back(num % base);
		num /= base;
	}
	long sum = 0;
	for (int i = 0; i < data.size(); i++)
		sum = sum * base + data[i];
	return sum;
}
int main()
{
	long num, res;
	int base;
	while (cin >> num)
	{
		if (num < 0)
			break;
		else
			cin >> base;
		res = numreverse(num, base);
		if (isPrimer(num) && isPrimer(res))
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
	}
	return 0;
}

发表于 2017-04-28 21:38:15 回复(0)

尤鱼哥

//没啥难点，看懂题目就行。另外牛客的测试怎么只有一个输入点？搞错了吧？
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	public static int reverse(int i,int d){
		ArrayList<Integer> list=new ArrayList<Integer>();
		while(i!=0){
			list.add(i%d);
			i=i/d;
		}
		int sum=0;
		for(int j=0;j<list.size();j++){
			sum=sum*d+list.get(j);
		}
		return sum;
	}
	public static 	boolean isprime(int m){
		Boolean f=true;
		if(m==1) return false;
		if(m==2) return f;
		for(int i=2;i<Math.sqrt(m);i++){
			if(m%i==0){
				f=false;
				break;
			}
		}
		return  f;
	}

	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		int n;
		while((n=in.nextInt())>0){
			int d=in.nextInt();
			if(isprime(n)&&isprime(reverse(n, d))){
				System.out.println("Yes");
			}else System.out.println("No");
		}
	}

}

发表于 2016-10-29 09:05:15 回复(0)

猫猫猫1

水题而已😅
#include<bits/stdc++.h>
using namespace std;

const int Max=1e6;
int Prime[Max],num;
bool p[Max];

void f() {
    p[0]=1;
    p[1]=1;
	for(int i=2; i<Max; i++) {
		if(!p[i]) {
			Prime[num++]=i;
		}
		for(int j=i+i; j<Max; j+=i) {
			p[j]=1;
		}
	}
}

int main() {
	f();
	int n,radix;
	while(cin>>n) {
		vector<int> v;
		if(n<0) {
			break;
		}
        cin>>radix;
		if(!p[n]) {
			while(n) {
				v.emplace_back(n%radix);
				n/=radix;
			}
			int m=v.size(),sum=0;
			for(int i=0; i<m; i++) {
				sum=radix*sum+v[i];
			}
			if(!p[sum]) {
				cout<<"Yes"<<endl;
			} else {
				cout<<"No"<<endl;
			}
		} else {
			cout<<"No"<<endl;
		}
	}
	return 0;
}

发表于 2022-11-15 12:04:36 回复(0)

牛客376907921号

菜鸡解法（没有打印素数表节省时间）

#include<cstdio>
#include<math.h>
bool isprime(int n){
	if(n<2) return false;
	for(int i=2;i<=sqrt(n*1.0);i++)
		if(n%i==0) return false;
	return true;
}
int change(int n,int d){
	int a=0;
	while(n){
		a=a*d+n%d;
		n/=d;
	}
	return a;
}
int main(){
	int n,d;
	while(1){
		scanf("%d", &n);
		if(n<0) return 0;
		scanf("%d", &d);
		isprime(n)&&isprime(change(n,d))?printf("Yes\n"):printf("No\n");
	}
}

发表于 2021-01-27 21:40:34 回复(0)

11122222222222222222

def baseN(num,d):
    return ((num==0) and '0') or (baseN(num/d,d).lstrip('0')+'0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'[num%d])
def toOtc(num,d):
    return (not num and '0') or (int(num[-1])+int(toOtc(num[:len(num)-1],d))*d)
def is_prime(num):
    return num>1 and all(num%d for d in range(2,int(num**.5)+1))
while True:
try:
num,d=map(int,raw_input().split())
print 'Yes' if is_prime(num) and is_prime(toOtc(baseN(num,d)[::-1],d)) else 'No'
except:
break

还有更短的吗

发表于 2019-01-17 10:46:21 回复(0)

τ20180907

预制质数表做大一点，否则反转之后转十进制的数有可能超过10^5，会出现segmentation fault

发表于 2018-10-04 17:33:40 回复(0)

C/C++

Caffeine

说实话这道题真的很难理解：
1.所有对于素数的判断都是基于10进制的。
2.对于数的反转应该是  num --> 先转换为给定进制的数 --> 再转换为反向给定进制的10进制
#include <iostream>
#include <stack>
#include <vector>
#include <string>
#include <math.h>
#include <sstream>
using namespace std;

bool IsPrime(long long x)
{
    bool check = true;
    if (x == 0 || x == 1)
    {
        check = false;
    }
    for (int i = 2; i <= sqrt(x); i++)
    {
        if (x % i == 0)
        {
            check = false;
        }
    }
    return check;
}

long long ReversePrime(long long x, int d)
{
    vector<int> tmp;
    while (x)
    {
        tmp.push_back(x % d);
        x = x / d;
    }
    long long temp=0;
    string tmpStr;
    for (int i = 0; i < tmp.size(); i++)
    {
        temp = temp * d + tmp[i];
    }

    return temp;
}

int main()
{
    int n,d;
    while (cin >> n)
    {
        if (n < 0)
        {
            return 0;
        }
        cin >> d;
        if (IsPrime(n))
        {
            long long rlt = ReversePrime(n, d);
            //cout << rlt << endl;
            if (IsPrime(rlt))
            {
                cout << "Yes" << endl;
            }
            else
            {
                cout << "No" << endl;
            }
        }
        else
        {
            cout << "No" << endl;
        }
    }
}

发表于 2018-08-23 09:36:02 回复(0)

carson0408

明白进制转换以及注意判断质数就行
#-*—coding:utf-8 -*-
def isprime(n):
    if n<=1:
        return False
    i=2
    while i*i<=n:
        if n%i==0:return False
        i+=1
    return True
def trans(N,D):
    s=[]
    while N>0:
        a=N%D
        N=N//D
        s.append(a)
    ls=len(s)
    ans=0
    for i in xrange(ls):
        ans+=s[i]*(D**(ls-1-i))
    return ans
while True:
    try:
        flag=False
        while not flag:
            m=map(int,raw_input().split())
            if m[0]<0:flag=True
            else:
                res=trans(m[0],m[1])
                if isprime(res) and isprime(m[0]):print 'Yes'
                else:print 'No'
    except:break

发表于 2017-07-24 09:56:15 回复(0)

新世纪的神

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int n,radix,num[20];
bool is_prime(int m){
    if(m==1)
        return false;
    int t=sqrt(m);
    for(int i=2;i<=t;i++){
        if(m%i==0)
            return false;
    }
    return true;
}
int reverse_prime(int m,int radix){
    int len=0,ans=0;
    while(m){
        num[len++]=m%radix;
        m/=radix;
    }
    for(int i=0;i<len;i++){
        ans=ans*radix+num[i];
    }
    return ans;
}
int main(){
    while(scanf("%d",&n)==1&&n>0){
        scanf("%d",&radix);
        int m=reverse_prime(n,radix);
        //printf("m==%d\n",m);
        if(is_prime(n)&&is_prime(m)){
            puts("Yes");
        }
        else{
            puts("No");
        }
    }
    return 0;
}

发表于 2016-07-24 14:03:01 回复(0)

啥

关键在于理解基的含义：

树A在基d下的表示A1，然后把A1倒置得到B（这两步可合成一步求）。然后求B是不是也是素数

def reverseNumber(n, d):
    x = 0
    while n:
        x = x*d + n%d
        n = n/d
    return x

def isPrime(n):
    if n<2:
        return False
    if n == 2:
        return True
    if n%2 == 0:
        return False
    i = 3
    while i*i <= n:
        if n%i == 0:
            return False
        i += 2
    return True

while True:
    try:
        n, d = map(int, raw_input().split())
        if isPrime(n) and isPrime(reverseNumber(n, d)):
            print "Yes"
        else:
            print "No"
    except:
        break

发表于 2016-02-22 09:44:20 回复(0)