n=int(input()) flag=1 # 填充的数字 cnt=1 # 下一个要填充数字的位置 x,y=0,0 g=[[0]*n for i in range(n)] while cnt<=n*n: # 先向右上角填充，一直填充到 出了上边界或者右边界 while x>=0 and y<n: g[x][y]=cnt cnt+=1 x-=1 y+=1 # 到边界后向下移动一格 x+=1 # 如果向下移动一格之后，y仍然出界，说明在对角线，那么向左下方移动一次 if y>=n: x+=1 y-=1 # 向左下角填充，一直填充到 出了下边界或者左边界 while x&lt...

埃氏筛 首先标记所有数字都是质数，然后如果x是质数，分别标记2*x 3*x,... 为非质数，然后使用前缀和，求得前i个数中质数的数量，保证后面的n个询问都能以O(1)的时间回答出来 N=1000010 primes=[1]*(N+1) primes[0]=primes[1]=0 i=2 while i*i<=N: j=2 while i*j<=N: primes[i*j]=0 j+=1 i+=1 for i in range(N): primes[i]+=primes[i-1] n=int(input()) for i in range(n): print(primes[int(...

11