XJOI一级九段1201题解

Question

xjoi上第1级9段的1201有其他的优化方案吗？
代码如下（c++）

#include<bits/stdc++.h>
using namespace std;
int n,t,s;
bool b[1000001];
void zhishu(void)
{
    memset(b,true,sizeof(b));
    b[1]=b[0]=false;
    for(int i=2;i<=1000000;i++)
      if(b[i])
        for(int j=i+i;j<=1000000;j+=i)
          b[j]=false;
      else
        continue; 
    return;
}
int main()
{
    zhishu();
    cin>>t;
    while(t--)
    {
        cin>>n;
          for(int i=2;i<=n;i++)
            if(b[i])
              s++;
        cout<<s<<endl;
        s=0;
    }
    return 0;
}

Answer 1

• 你看下这篇博客吧, 应该有用👉 ：XJOI 3679 一道有趣的题 求解求解
• 除此之外, 这篇博客: XJOI一级二段题解（g++，即C++），也可视作C++算法竞赛教程中的 2.1 数轴与平面直角坐标系 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• 警告 大段概念来袭

  一条直线，若规定了它的原点、正方向和单位长度，就可称之为数轴。两条互相垂直的数轴，移动它们的原点，直到两原点重合，就形成了一个平面直角坐标系（如图所示）。

  

  如图，两个重合的原点被称为该坐标系的原点，一般我们规定一个平面直角坐标系由一根铅直的数轴和水平的数轴组成，铅直的数轴一般叫“y轴”，水平的数轴一般叫“x轴”。在实际应用中，可以调整两轴的正方向。

  若x轴的正方向朝右，y轴的正方向朝上，则右上角的区域叫“第一象限”，左上角的区域叫“第二象限”，左下角的区域叫“第三象限”，左上角的区域叫“第四象限”。四个象限按一-->二-->三-->四的顺序成逆时针排序。规定两坐标轴不属于任何象限。

  

  平面直角坐标系中，过一个点作x轴和y轴的平行线（若其在x轴或y轴上，则无需作该轴的平行线），将其看做数轴（原点相应地平移），则该点在平行于x轴上的对应点表示的数字叫做这个点的横坐标，在平行于y轴上的对应点表示的数字叫做这个点的纵坐标。该点在直角坐标系中的位置标示为“（横坐标，纵坐标）”。