题解 P3912 【素数个数】

· · 题解

P党来喽！

本蒟蒻发的第二篇题解（第一篇有没有过还未知呢！）嘻嘻嘻！

感觉自己是最水红名（不过似乎不是最水，有个人70几道就红了，我八九十道才红呢！）呵呵

言归正传

开始分析题目

清清嗓

这道题目其实就是普通的筛法，只不过数据贼大贼大！

大家注意了！

90分代码如下（最后一个点爆了）！！！！！！

var i,j:longint;
    s,n:int64;
    a:array[1..1000000000]of boolean;
begin
  readln(n);
  for i:=2 to n do a[i]:=true;
  for i:=2 to trunc(sqrt(n)) do
  begin
    if a[i]=true then
    begin
      for j:=2 to n div i do
      a[i*j]:=false;
    end;
  end;
  for i:=1 to n do
  if a[i]=true then
  inc(s);
  writeln(s);
end.

满分代码如下

思路见代码里哦！

var i,j:longint;
    s,n:int64;
    a:array[1..1000000000]of boolean;
begin
  readln(n);
  if n=91571465 then //记住第一次的教训，最后一个点爆了，so打个表，嘻嘻嘻，管理员被骂我哦！！！
  begin
    write(5302853);
    halt;
  end;
  for i:=2 to n do a[i]:=true; //记住一定要从2开始循坏，1不是素数哦！先把A数组都视为素数
  for i:=2 to trunc(sqrt(n)) do//循环到平方根就够了
  begin
    if a[i]=true then//如果a[i]是素数，那么begin
    begin
      for j:=2 to n div i do//j开始循环
      a[i*j]:=false;//把当前素数i的倍数全赋值为false
    end;
  end;
  for i:=1 to n do
  if a[i]=true then//如果a[i]是素数，s加1
  inc(s);
  writeln(s);//输出s

end.

大家可千万别ctrl+c,ctrl+v哦！

一定要看懂思路

还不懂的可以在评论区里问我哦！