题解 P3912 【素数个数】

丁俊哲djz · 2019-04-12 08:36:47 · 题解

这道题的数据贼大贼大的，所以我用了（欧拉筛法），时间复杂度基本上在O(n)，相信许多大佬早以使用了，所以我不做过多解释了。

【算法思路】

1.以t作为累加器。

2.（1)要特别注意，不能算进去。

3.如果i为合数则放弃这次查找。

【代码】如下:

var
  n,i,j,t:longint;
  b:array[1..100000001] of boolean;
  p:array[1..100000001] of longint;
  begin
    fillchar(b,sizeof(b),false);//b数组初始值为false
    readln(n);//输入
    t:=0;//累加器t清零

    for i:=2 to n do//开始欧拉筛法
    begin
       if b[i]=false then//如果b[i]的值为false则把i
       列为质数
       begin 
         inc(t);//累加质数个数
         p[t]:=i;          
       end;
       for j:=1 to t do
       begin
         if i*p[j]>n then break;//如果超出了范围，
         放弃这次接下来及这次的查找
         b[i*p[j]]:=true;//这个开始在排除合数
         if i mod p[j]=0 then break;//如果i已经被查找
         成为合数，则不用查找这次了。
       end;
    end;//一次筛法结束

    writeln(t);//输出
    end.