[LeetCode]Prime Palindrome

这道题第一个想法就是每次找下一个更大的回文，验证其是否是质数。找下一个最大回文的思路我们在Find the Closest Palindrome当中讲过，我们用相似的思路即可。时间复杂度不太清楚如何分析，代码如下：

	class PalinGenerator
	{
	public:
	PalinGenerator(int seed)
	{
	string s = to_string(seed);
	int rootLen = (s.size() + 1) / 2;
	string str = s.substr(0, rootLen);
	root = stoi(str);
	len = s.size();
	int palin = mirror(str, len % 2);
	if (palin < seed)increaseRoot();
	}
	int Next()
	{
	int res = mirror(to_string(root), len % 2);
	increaseRoot();
	return res;
	}
	private:
	int root, len;
	int mirror(string root, bool odd)
	{
	int rootLen = root.size();
	string r = root;
	if (odd)r.pop_back();
	reverse(r.begin(), r.end());
	return stoi(root + r);
	}
	bool reachMax(int root)
	{
	while (root)
	{
	if (root % 10 != 9)return false;
	root /= 10;
	}
	return true;
	}
	void increaseRoot()
	{
	if (reachMax(root))
	{
	++root;
	if (len % 2)root /= 10;
	++len;
	}
	else ++root;
	}
	};
	class Solution {
	public:
	int primePalindrome(int N) {
	if (N == 1)return 2;
	PalinGenerator pg(N);
	while (true)
	{
	int palin = pg.Next();
	if (isPrime(palin))return palin;
	}
	return -1;
	}
	private:
	bool isPrime(int num)
	{
	for (int i = 2; i * i <= num; ++i)
	{
	if (num % i == 0)return false;
	}
	return true;
	}
	};

view raw Prime Palindrome_1.cpp hosted with ❤ by GitHub

看了讨论区之后发现用数学的方法过滤一些数可以大大提高速度。因为所有长度为偶数的回文肯定不是质数(除了11)，因为对于一个数，奇数位上的数的和与偶数位的上的数的和之间的差可以被11整除的话(包括0)，这个数就可以被11整除。偶数长度的回文这个差值显然为0，所以必定可以被11整除，也就是说除了11之外，全都不是质数。那么我们在之前实现的基础上，不停get下一个回文的时候跳过所有长度为偶数的回文即可。代码如下：

	class PalinGenerator
	{
	public:
	PalinGenerator(int seed)
	{
	string s = to_string(seed);
	int rootLen = (s.size() + 1) / 2;
	string str = s.substr(0, rootLen);
	len = s.size();
	//skip even length palindrome
	if (len % 2)
	{
	root = stoi(str);
	int palin = mirror(str);
	if (palin < seed)increaseRoot();
	}
	else
	{
	++len;
	string tmp = "1" + string(rootLen, '0');
	root = stoi(tmp);
	}
	}
	int Next()
	{
	int res = mirror(to_string(root));
	increaseRoot();
	return res;
	}
	private:
	int root, len;
	int mirror(string root)
	{
	int rootLen = root.size();
	string r = root;
	r.pop_back();
	reverse(r.begin(), r.end());
	return stoi(root + r);
	}
	bool reachMax(int root)
	{
	while (root)
	{
	if (root % 10 != 9)return false;
	root /= 10;
	}
	return true;
	}
	void increaseRoot()
	{
	if (reachMax(root))
	{
	++root;
	len += 2;
	}
	else ++root;
	}
	};
	class Solution {
	public:
	int primePalindrome(int N) {
	if (N == 1)return 2;
	//11 is the only prime with even length
	if (N > 7 && N <= 11)return 11;
	PalinGenerator pg(N);
	while (true)
	{
	int palin = pg.Next();
	if (isPrime(palin))return palin;
	}
	return -1;
	}
	private:
	bool isPrime(int num)
	{
	for (int i = 2; i * i <= num; ++i)
	{
	if (num % i == 0)return false;
	}
	return true;
	}
	};

view raw Prime Palindrome_2.cpp hosted with ❤ by GitHub