埃筛里的一个问题，知道怎么改但是想不通为什么

Question

一个前缀和的题目，题干如下：
n是两个连续的奇素数的平均值，且n不是素数，那么我们称这样的数是"内部素数"。求区间[a,b]内"内部素数"的个数。比如，前5个"内部素数"是4,6,9,12,15。
我的代码如下：

#include<stdio.h>
#define N 1000010
typedef long long ll;
int t[N],tt[N],prime[N];
void init()
{
    int p=0;
    for(int i=2;i<N;i++)
    {
        if(!t[i]) prime[++p]=i;
        if(!t[i]&&i*i<N)
        {
            for(int j=i*i;j<N;j+=i)
            t[j]=i;
         } //埃筛，得到质数数组prime 
    }
    for(int i=2;i<p;i++)
    {
        tt[(prime[i]+prime[i+1])/2]=1;
    }
    for(int i=1;i<N;i++)
    {
        tt[i]=tt[i]+tt[i-1];
    }
}
int main()
{    
    init();
    int T;
    int a,b;
    scanf("%d",&T);
    while(T--)
    {    
        scanf("%d %d",&a,&b);
        printf("%d\n",tt[b]-tt[a-1]);
    }
    return 0;
}

这个程序运行时会崩溃，如果把if(!t[i]&&i*i<N)改为if(!t[i]&&i<N/i),程序就可以正确运行，想知道原因是什么。

Answer 1

该回答引用ChatGPT

程序中的第一个筛选质数的循环使用的是埃式筛法，而在筛选过程中，如果$i$不是质数，但是$t[i]$的值仍然为0，则说明$i$的倍数还未被标记，此时会重复标记同一个数，因此会影响后面的计算，导致程序出现错误。这个问题在 $i > \sqrt{N}$ 时尤为突出。

为了避免这种重复标记的问题，需要将第一个循环中的条件从 if(!t[i]&&i*i<N) 改为 if(!t[i])，然后将第二个循环的起始值 $i^2$ 改为 $2i$，这样就可以避免重复标记同一个数了。修改后的代码如下：

using System;

class Program {
    static void Main(string[] args) {
        const int N = 1000010;
        int[] t = new int[N];
        int[] tt = new int[N];
        int[] prime = new int[N];
        int p = 0;
        for (int i = 2; i < N; i++) {
            if (t[i] == 0) {
                prime[++p] = i;
            }
            for (int j = 1; j <= p && i * prime[j] < N; j++) {
                t[i * prime[j]] = 1;
                if (i % prime[j] == 0) {
                    break;
                }
            }
        }
        for (int i = 2; i < p; i++) {
            tt[(prime[i] + prime[i + 1]) / 2] = 1;
        }
        for (int i = 1; i < N; i++) {
            tt[i] = tt[i] + tt[i - 1];
        }
        int T = int.Parse(Console.ReadLine());
        while (T-- > 0) {
            string[] input = Console.ReadLine().Split();
            int a = int.Parse(input[0]);
            int b = int.Parse(input[1]);
            Console.WriteLine(tt[b] - tt[a - 1]);
        }
    }
}

这里使用的是线性筛法，不仅可以避免重复标记，而且还可以减少筛选质数的时间复杂度。