回文素数

题目描述
因为 151 既是一个质数又是一个回文数（从左到右和从右到左是看一样的），所以 151 是回文质数。
写一个程序来找出范围[a,b] (5≤a<b≤100,000,000)( 一亿)间的所有回文质数。
输入格式
第 1 行: 二个整数 a 和 b .
输出格式
输出一个回文质数的列表，一行一个。
输入输出样例
输入
5 500
输出
5
7
11
101
131
151
181
191
313
353
373
383

由于所有四位，六位，八位的回文数均是11的倍数，所以这些位的数字一定不是素数，一亿是一个九位的数，因此只需要判断一位，二位，三位，五位，七位的回文质数，构造回文数的时候由于最低位只能是奇数，因此最高位从1开始，每次加2。
如果从1开始暴力不知道会t多少次，这样复杂度为o（n*logn）,如果枚举所有回文数再判断素数复杂度为o（sqrt（n））
代码如下：

#include<bits/stdc++.h>
using namespace std;
bool is_prime(int n)  //判断素数
{
	if (n == 2)
		return true;
	if (n % 2 == 0)
		return false;
	for (int i = 3;i<=sqrt(n);i+= 2)
	{
		if (n % i == 0)
		{
			return false;
		}
	}
	return true;
}
int len(int n)  //判断区间数据长度的函数
{
	int length = 1;
	while (n > 9)
	{
		n /= 10;
		length++;
	}
	return length;
}
int main()
{
	int b, e;  //开始与结束的区间
	int len_b, len_e;  //两区间数字的位数
	cin >> b >> e;
	len_b = len(b);
	len_e = len(e);
	if (len_b <= 1 && len_e >= 1)
	{
		if (b <= 5 && e >= 5)
			cout << "5" << endl;
		if (b <= 7 && e >= 7)
			cout << "7" << endl;
	}
	if (len_b <= 2 && len_e >= 2)
	{
		if (b <= 11 && e >= 11)
			cout << "11" << endl;
	}
	if (len_b <= 3 && len_e >= 3)
	{
		for (int i = 1;i <= 9;i += 2)
		{
			for (int j = 0;j <= 9;j++)
			{
				int num = 100 * i + 10 * j + i;
				if (num < b)
					continue;
				if (num > e)
					break;
				if (is_prime(num))
					cout << num << endl;
			}
		}
	}
	if (len_b <= 5 && len_e >= 5)
	{
		for (int i = 1;i <= 9;i += 2)
		{
			for (int j = 0;j <= 9;j++)
			{
				for (int k = 0;k <= 9;k++)
				{
					int num = 10000 * i + 1000 * j + 100 * k + 10 * j + i;
					if (num < b)
						continue;
					if (num > e)
						break;
					if(is_prime(num))
						cout<<num<<endl;
				}
			}
		}
	}
	if (len_b <= 7 && len_e >= 7)
	{
		for (int i = 1;i <= 9;i += 2)
		{
			for (int j = 0;j <= 9;j++)
			{
				for (int k = 0;k <= 9;k++)
				{
					for (int l = 0;l <= 9;l++)
					{
						int num = 1000000 * i + 100000 * j + 10000 * k + 1000 * l + 100 * k + 10 * j + i;
						if (num < b)
							continue;
						if (num > e)
							break;
						if (is_prime(num))
							cout << num << endl;
					}
				}
			}
		}
	}
	return 0;
}