若整数i从左向右读与从右向左读是相同的数,且i为素数,此时称其 为回文素数。所谓素数是指只能由1和它本身整除的整数。 对于偶数位的整数,只有11是回文素数。也就是说,除了11以外, 所有的2位整数都不是回文素数。所有的4位整数、6位整数、8位整数中 也不存在回文素数。但是三位回文素数有很多,比如:101、131、151、 181、191、313等。本案例要求通过编程求出所有小于1000的回文素数。
时间: 2023-05-30 11:01:39 浏览: 78
解法一:暴力枚举
首先,我们需要判断一个数是否为素数,可以使用试除法。具体实现时,只需要从2到这个数的平方根进行枚举,判断是否能整除即可。如果都不能整除,那么这个数就是素数。
其次,我们需要判断一个数是否为回文数,可以将这个数转化为字符串,然后判断其翻转后是否与原来的字符串相等即可。
综上,我们可以使用两层循环来枚举所有小于1000的回文素数。
代码实现:
```python
def is_prime(n):
if n < 2:
return False
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return True
def is_palindrome(n):
return str(n) == str(n)[::-1]
for i in range(1, 1000):
if is_palindrome(i) and is_prime(i):
print(i)
```
解法二:优化枚举
观察题目中的数据范围,我们发现只有小于1000的数需要判断是否为回文素数,因此可以进一步优化枚举的范围。
具体实现时,我们首先枚举所有小于100的回文数,然后在每个回文数的基础上依次枚举其余两位,判断是否为素数即可。
代码实现:
```python
def is_prime(n):
if n < 2:
return False
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return True
def is_palindrome(n):
return str(n) == str(n)[::-1]
for i in range(1, 10):
if is_palindrome(i):
print(i)
for i in range(1, 10):
if is_palindrome(i * 11):
print(i * 11)
for i in range(1, 10):
for j in range(10):
if is_palindrome(i * 101 + j * 10):
print(i * 101 + j * 10)
for i in range(1, 10):
for j in range(10):
if is_palindrome(i * 1001 + j * 110):
print(i * 1001 + j * 110)
```
以上两种方法的时间复杂度均为O(n^2),但是优化枚举的方法在实际运行中会更快。