Path: newsspool2.news.pas.earthlink.net!stamper.news.pas.earthlink.net!elnk-nf2-pas!newsfeed.earthlink.net!newshub.sdsu.edu!headwall.stanford.edu!newsfeed.stanford.edu!postnews1.google.com!not-for-mail
Message-ID: <d7f57098.0309151659.31c1adb@posting.google.com>
From: Jason628@hotmail.com (Jason Rodgers)
Newsgroups: sci.math
Subject: Re: Last Call For Primecounters
Date: 15 Sep 2003 17:59:17 -0700
References: <m7bc31-pkc.ln1@lexi2.athghost7038suus.net>
Lines: 90
Organization: http://groups.google.com/
NNTP-Posting-Host: 68.47.81.114
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
X-Trace: posting.google.com 1063673958 21041 127.0.0.1 (16 Sep 2003 00:59:18 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: 16 Sep 2003 00:59:18 GMT
X-Received-Date: Mon, 15 Sep 2003 17:59:19 PDT (newsspool2.news.pas.earthlink.net)
Xref: lexi2.athghost7038suus.net sci.math:38183

Here is mine.  I know it is not the fastest but it still beats my old code.

-------------------

class bit
{
	
	char *bitarray;
        char list[8];

        public:
		
	bit(unsigned long long length)
	{
		length=(length+1)/8;
		bitarray=new char[length];
		for(unsigned long long i=0;i<length;i++)bitarray[i]=0;
                list[0]=1;
                list[1]=2;
                list[2]=4;
                list[3]=8;
                list[4]=16;
                list[5]=32;
                list[6]=64;
                list[7]=128;               
  
	}
	
	~bit(){delete bitarray;}

	
	void biton(unsigned long long pos)
	{
                unsigned long long rec = pos/8;
                bitarray[rec]=(bitarray[rec] | list[pos%8]);
	}

	void bitflip(unsigned long long pos)
	{
		unsigned long long rec = pos/8;
		bitarray[rec]=(bitarray[rec] ^ list[pos%8]);
	}

	char bitvalue(unsigned long long pos)
	{
		unsigned long long rec = pos/8;
		return (bitarray[rec] & list[pos%8]);
	}
        
};

#include <iostream>
#include <stdio.H>

inline unsigned long long pi(unsigned long long);

int main (int argc, const char * argv[]) {

    using namespace std; //introduces namespace std
    
    const unsigned long long n = 3900000;
    
    std::cout<<"Pi("<<n<<") ="<<pi(n+1);    

    return 0;
}

inline unsigned long long pi(unsigned long long n)
{
    unsigned long long sqrtn = sqrt(n+0.)+1;    
    
    unsigned long long i,k,an,start = 1;

    bit a(n);    

   for(i=4;i<n;i+=2)a.biton(i);

    while(start <= sqrtn)
    {
	start+=2;
	while(a.bitvalue(start) and start<=sqrtn)start+=2;    
	for(i=start*start;i<n;i+=start)a.biton(i);
    }
    
    an = 1;
    for(k=3;k<n;k+=2)an+=!a.bitvalue(k);
    
    return an;

}