南宁百度推广电话_网站设计师薪资参考_西安seo外包优化_免费网站安全软件下载

目录

牛客_BC157素数回文_数学

题目解析

C++代码

Java代码

---

牛客_BC157素数回文_数学

素数回文_牛客题霸_牛客网

描述：

现在给出一个素数，这个素数满足两点：

1、  只由1-9组成，并且每个数只出现一次，如13,23,1289。

2、  位数从高到低为递减或递增，如2459，87631。

请你判断一下，这个素数的回文数是否为素数（13的回文数是131,127的回文数是12721）。

输入描述：

输入只有1行。

第1行输入一个整数t，保证t为素数。

数据保证：9<t<10^9

输出描述：

输出一行字符串，如果t的回文数仍是素数，则输出“prime”，否则输出"noprime"。

---

题目解析

        如果p是一个质数，而且整数a与p互质（即最小公因数gcd(a,p)=1），则有a^(p−1)≡1(mod p)（模p同余符号）。但是这个命题的逆命题不一定能判断一个数是否为素数，只能说明不满足a^(p−1)≡1(mod p)条件的 p 一定是合数。在本算法里，主要就是运用了它的逆命题来检验素数的。

C++代码

#include <cmath>
#include <cstdlib>
#include <iostream>
using namespace std;bool isPrime(long long n)
{if(n < 2)return false;for(int i = 2; i <= sqrt(n); ++i){if(n % i == 0)return false;}return true;
}int main()
{string str;cin >> str;string tmp = str;for(int i = str.size() - 2; i >= 0; --i){tmp += str[i];}long long n = atoll(tmp.c_str()); // to long long!!!// cout << n << " ";if(isPrime(n))cout << "prime" << endl;elsecout << "noprime" << endl;return 0;
}

Java代码

import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{public static long change(String s){StringBuffer tmp = new StringBuffer(s);for(int i = s.length() - 2; i >= 0; i--){tmp.append(s.charAt(i));}return Long.parseLong(tmp.toString());}public static boolean isprim(long x){if(x <= 1)return false;for(long i = 2; i <= Math.sqrt(x); i++){if(x % i == 0)return false;}return true;}public static void main(String[] args) {Scanner in = new Scanner(System.in);String s = in.next();long x = change(s);if(isprim(x))System.out.println("prime");elseSystem.out.println("noprime");}
}