算法刷题记录：素数回文-526互联

题目链接

https://ac.nowcoder.com/acm/contest/19859/C

题目分析

构造一个回文数，然后去判就行了。

AC代码

// Problem: 素数回文
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/19859/C
// Memory Limit: 65536 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <cmath>

using namespace std;
typedef long long ll;
const int N = 7000010;

ll n, cnt;
int st[N], p[N];

int main()
{
	for (int i = 2; i <= N; ++ i)
		if (!st[i])
		{
			p[cnt ++ ] = i;
			for (int j = i + i; j <= N; j += i)
				st[j] = true;
		}
	
	ll t; cin >> n;
	t = n / 10; 

	// 构造一个素数的回文
	while (t) n *= 10, n += t % 10, t /= 10;
    
	bool flag = true;
	for (int i = 0; i < cnt; ++ i)
	{
		int pr = p[i];
		if (pr >= sqrt(n)) break;
		if (n % pr == 0) {flag = false; break; }
	}
		
	if (!flag) cout << "noprime" << endl;
	else cout << "prime" << endl;
	return 0;
}