rsss

时间限制:1秒  内存限制: 128 MB

试题描述

    在质数的大家庭中，大小之差不超过2的两个质数称它俩为一对孪生素数，如2和3、3和5、17和19等等。请你统计一下，在不大于自然数N的质数中，孪生素数的对数。

输入要求

    输入文件rsss.in只有一行，一个自然数N。(N<=10^6)

输出要求

    输出文件rsss.out只有一行，一个整数，表示N以内孪生素数的对数。

输入样例

20

输出样例

5

知识点及提示

打印素数表的方法0.0

 

Var i,j,n,l,k:longint;

    p:array[1..1000000]of boolean;

    pt:Array[1..100000]of longint;

function pr(l:longint):boolean;

var kk:longint;

begin

  for kk:=1 to trunc(sqrt(l)) do if (l mod i=0) and (l<>kk) then exit(true);

  exit(false);

end;

begin

  fillchar(p,sizeof(p),true);

  i:=2;

  readln(n);

  i:=2;

  while i<=n do

  begin

        if p[i] then

        begin

        j:=i*2;

        while j<=n do

        begin p[j]:=false; inc(j,i); end;

        end;

        inc(I);

  end;

  l:=0;

  for i:=1 to n do if p[i] then

  begin

    inc(l);

    pt[l]:=i;

  end;

  if not pr(n) then begin

    inc(l);

    pt[l]:=n;

  end;

  for i:=2 to  l do if (pt[i+1]-pt[i]<=2)and (pt[i+1]<>0) and(pt[i]<>0) then  inc(k);

  writeln(k);

end.