A113156.皓仔的质数数位和

普及-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

皓仔最近在研究一种特殊的数字。

对于一个正整数 xx,定义一次操作为:把 xx 的每一位数字相加,得到一个新的数。

例如:

  • 2929 进行一次操作,得到 2+9=112+9=11
  • 1111 再进行一次操作,得到 1+1=21+1=2

如果一个数不断进行这样的操作,直到变成一位数为止,并且在这个过程中出现的每一个数都是质数,那么皓仔就称这个数为“好数”。

例如:

  • 2911229 \to 11 \to 2,过程中每个数都是质数,所以 2929 是好数;
  • 8917889 \to 17 \to 8,最后出现了 88,不是质数,所以 8989 不是好数。
  • 16716 \to 7, 最开头出现了 1616, 不是质数,所以 1616 不是好数。

现在给定两个整数 llrr,请你求出区间 [l,r][l,r] 中一共有多少个好数。

输入格式

输入一行,包含两个整数 llrr

输出格式

输出一个整数,表示区间 [l,r][l,r] 中好数的个数。

输入输出样例

  • 输入#1

    1 100

    输出#1

    12

说明/提示

【样例解释】

11100100 中,符合条件的数有:

2,3,5,7,11,23,29,41,43,47,61,832,3,5,7,11,23,29,41,43,47,61,83

所以答案为 1212
【数据范围】

对于所有测试点,保证:

  • 1lr1051 \le l \le r \le 10^5
首页