当前位置: 代码迷 >> 综合 >> LightOJ - 1197 Help Hanzo(埃氏素筛在线求区间素数个数)
  详细解决方案

LightOJ - 1197 Help Hanzo(埃氏素筛在线求区间素数个数)

热度:15   发布时间:2023-12-09 20:15:47.0

链接:LightOJ - 1197 Help Hanzo

题意:

T ( ≤ 200 ) T(\le 200) T(200)组数据,每组数据给出 a , b &ThickSpace; ( 1 ≤ a ≤ b &lt; 2 31 , b ? a ≤ 100000 ) a,b\;(1\le a\le b\lt2^{31},b-a\le 100000) a,b(1ab<231,b?a100000),问区间 [ a , &ThinSpace; b ] [a,\,b] [a,b]内有多少素数?



分析:

预处理所有素数会TLE+MLE,所以要利用条件“ b ? a ≤ 100000 b-a\le 100000 b?a100000 ”,于是我们可以每次对区间进行埃氏素数筛选,得到这个区间内的素数表(即得到了素数个数)。

就像判断 n n n是否为素数需要 1 1 1 ~

  相关解决方案