Path: newsspool2.news.pas.earthlink.net!stamper.news.pas.earthlink.net!elnk-pas-nf1!newsfeed.earthlink.net!news.maxwell.syr.edu!newsfeed.icl.net!newsfeed.fjserv.net!news.netkonect.net!dnews0.news.legend.net.uk!not-for-mail
Message-ID: <3f54d206@dnews0.news.legend.net.uk>
From: "Carl W." <root@127spam.0.0.1>
Newsgroups: sci.math
Subject: Re: Harris, eat this: Vastly superior prime counting function
Date: Tue, 02 Sep 2003 18:25:19 +0100
References: <christian.bau-7F4291.23461901092003@slb-newsm1.svr.pol.co.uk>
Lines: 25
Organization: Messy. Bits of paper all over.
NNTP-Posting-Host: news.legend.co.uk
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit
X-Trace: news.netkonect.net 1062595210 4310 212.41.160.119 (3 Sep 2003 13:20:10 GMT)
X-Complaints-To: usenet@news.netkonect.net
NNTP-Posting-Date: Wed, 3 Sep 2003 13:20:10 +0000 (UTC)
User-Agent: Mozilla/5.0 (Windows; U; WinNT4.0; en-US; rv:1.4) Gecko/20030624
X-Accept-Language: en, en-us
In-Reply-To: <christian.bau-7F4291.23461901092003@slb-newsm1.svr.pol.co.uk>
X-Original-NNTP-Posting-Host: nat.office.legend.net.uk
X-Original-Trace: 2 Sep 2003 18:23:18 +0100, nat.office.legend.net.uk
X-Received-Date: Wed, 03 Sep 2003 06:20:11 PDT (newsspool2.news.pas.earthlink.net)
Xref: lexi2.athghost7038suus.net sci.math:35425

Ignoring the fact this particular algorithm hunt is frivolous (as long 
as we stick to sieve variants)... The following is fast and seems to be 
equivalent to the originally cited pi():

   typedef  unsigned long long  Integer;  /* I like sugar */

   Integer pi (Integer x) {

      Integer i, j, k, sum = 2;
      unsigned short int ti, tj;

      if (x<2) return 0;
      if (x<3) return 1;
      if (x<5) return 2;

      for (i = 5, ti = 4; i <= x; i += (ti = 6 - ti), sum += k) {
         for (j = 5, tj = 4, k = 1; j * j <= i; j += (tj = 6 - tj))
            if (i % j == 0) { k = 0; break; }
      }

      return sum;
   }

Carl