有这样一种整数,它自身是素数,它有MV,如果它的高n减一位也是素数。则这种树被称为左高阶素数,比如11001673是素数,它有八位。它的高七位1100167也是素数,类似的数据还有2113和211。2273和22711002499和1100249等。给定一个区间st,其中10小于s小于t<1万,求出该区间所有所高阶素数的个数。在100~200中,这样的左高阶速数有100个,在200~300中这样的左高阶速数有三输入格式一行两个整数st表示区间,其实之后终止值,中间以空格分隔。输入格式一个正整数,表示该区间左高级所述的数目。个。,
时间: 2024-03-24 13:38:00 浏览: 124
以下是Python的实现代码:
```python
# 素数筛选法
def get_primes(n):
primes = [True] * (n + 1)
primes[0] = primes[1] = False
for i in range(2, int(n ** 0.5) + 1):
if primes[i]:
for j in range(i ** 2, n + 1, i):
primes[j] = False
return primes
# 数位DP
def dfs(p, digit, primes, memo):
if digit == 1:
return 1
if (p, digit) in memo:
return memo[(p, digit)]
memo[(p, digit)] = 0
for i in range(1, 10):
q = i * (10 ** (digit - 1)) + p // 10
if q >= 10 and primes[q]:
memo[(p, digit)] += dfs(q, digit - 1, primes, memo)
return memo[(p, digit)]
# 主函数
def count_left_truncatable_primes(s, t, mv):
primes = get_primes(t)
cnt = 0
for i in range(10, t):
if primes[i] and dfs(i, mv, primes, {}) > 0:
if i >= s:
cnt += 1
return cnt
# 测试
s, t, mv = map(int, input().split())
print(count_left_truncatable_primes(s, t, mv))
```
其中,`get_primes`函数使用素数筛选法预处理出区间[0,t]内的所有素数,并将它们存储在一个布尔类型的数组`primes`中,`True`表示该下标对应的数是素数,`False`表示它不是素数。`dfs`函数使用数位DP的方法,从最高位到最低位枚举每个长度为mv的数字,并依次判断它是否为左高阶素数。`memo`字典用于记录已经计算过的状态。
最后,`count_left_truncatable_primes`函数调用`get_primes`和`dfs`函数,计算出区间[s,t]内的左高阶素数个数。
阅读全文