Solved

Prime Number Table - Constant Seach Time

Posted on 2006-10-22
11
341 Views
Last Modified: 2012-06-21
After a question with sunnycoder about searchtimes of sorted arrays, I've decided to try something out.

I want to be able to determine if a number is prime, a number between (1-10,000,000) in a constant period of time.

How I plan to do this is I'm going to make a list of prime numbers between 1-10,000,000 in an array.

So it would make sense to use an array with 10,000,000 boolean elements, but this is really overkill, since all i need is a single bit and not an 8bit boolean.

So what I was thinking was making an array of 10,000,000/32  elements, because each bit of the 32bit number can represent the boolean value for the number being prime. So for example, say I wanted to determine if the number 17 was prime, I would only need a single 32bit number, where the each bit was set corresponding to the number being prime or not so it would be something like: 0010101000101001010001000001010, does this make sense?
                                                                                                                     3  5  7    11 13 17 19  23       29  31

So since I know which bit in the number corresponds to 17 being prime or not, its rather trivial to determine whether or not 17 is prime.

The reason i'm doing it this way is just because I want to minimize the size of the array. Where with 8bit values i would have 10,000,000 bytes, by doing it like this the array size would become something like 10,000,000 / 8bits or around 1,250,000 bytes around (1mb vs 10mb).

Make sense?

I'm not really sure how to go about something like this. Figuring out if a number is prime seems pretty simple...

  value = primeTable[(Number / 32)]
  bitPosition =  (Number % 32)
  bitValue = ((Number << bitPosition) & 0x1) //right? Shift all the way to the right and bitwise and with 1???


The confusion I am having is about how to build this array, any suggestions would be appriciated.



Thanks.
Brian
     

0
Comment
Question by:BrianGEFF719
  • 8
  • 2
11 Comments
 
LVL 19

Author Comment

by:BrianGEFF719
ID: 17786503
Sorry my example should be:

bitValue = ((value << bitPosition) & 0x1) //right? Shift all the way to the right and bitwise and with 1???
0
 
LVL 84

Expert Comment

by:ozo
ID: 17786509
value = primeTable[Number/8]>>number%8 & 1;
0
 
LVL 19

Author Comment

by:BrianGEFF719
ID: 17786533
>>value = primeTable[Number/8]>>number%8 & 1;
I'm using 32bit longs though, should I just use single bytes?

for example suppose I was doing it like this:

      unsigned long primeTable = 0;
      int maxPrime = sizeof(unsigned long) * 8;

      for (int i = 1; i < maxPrime; ++i)
      {
            if (isPrime(i))
            {
                  //how would I set the corresponding bit?
            }
      }
0
 
LVL 19

Author Comment

by:BrianGEFF719
ID: 17786536
Would it be:

primeTable += i * i; ???
0
 
LVL 19

Author Comment

by:BrianGEFF719
ID: 17786543
Oh wait, I think i've got that part now:

primeTable += (1 << (i-1));
0
IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

 
LVL 19

Author Comment

by:BrianGEFF719
ID: 17786548
This seems to work:

      unsigned long primeTable = 0;
      unsigned long temp = 0;
      int maxPrime = sizeof(unsigned long) * 8;

      for (int i = 1; i < maxPrime; ++i)
      {
            if (isPrime(i))
            {
                  primeTable += (1 << (i-1));
            }
      }

      for (i = 1; i < maxPrime; ++i)
      {
            temp = primeTable;
            if ( (temp >> (i - 1) & 1) )
            {
                  cout << i << " is prime" << endl;
            }
      }
0
 
LVL 19

Author Comment

by:BrianGEFF719
ID: 17786623
So here is the code i've come up with so far:


void main (void)
{
      long startTick,endTick,longSize=sizeof(unsigned long)*8;
      long maxPrime = 1000000;
      unsigned long *pTable;
      int numItems = (maxPrime / longSize) + 1;

      cout << numItems << " " << longSize << "bit array elements will be needed for " << maxPrime << " items " << endl;

      if ( (pTable = (unsigned long *) malloc(numItems)) == NULL)
      {
            cout << endl <<  "ERROR: Unable to allocate memory." << endl;
            exit(-1);
      }

      startTick = GetTickCount();
      cout << "Building array...";
      
      for (long i = 1; i < maxPrime; ++i)
      {
            if (isPrime(i))
            {
                  *(pTable + (i / longSize)) += (1 << ((i % 32)));
            }
      }
      
      endTick = GetTickCount();
      cout << "Done building array, Time: " << (endTick - startTick) << "ms" << endl;

      cout << endl << endl;
      system("PAUSE");
}


I'm getting an error on the line *(pTable + (i / longSize)) += (1 << ((i % 32)));, Unhandled Exception, not really sure why.


-Brian
0
 
LVL 19

Author Comment

by:BrianGEFF719
ID: 17786676
Here is my most recent version, for some reason its not  working properly and i cannot figure out why:


void main (void)
{
      long theNumber,startTick,endTick,longSize = sizeof(unsigned long) * 8,maxPrime = 1000000;
      unsigned long *pTable;
      int isItPrime,numItems = (maxPrime / longSize) + 1;

      cout << numItems << " " << longSize << "bit array elements will be needed for " << maxPrime << " items " << endl;

      if ( (pTable = new unsigned long[numItems]) == NULL)
      {
            cout << endl <<  "ERROR: Unable to allocate memory." << endl;
            exit(-1);
      }

      startTick = GetTickCount();
      cout << "Building array...";
      
      for (long i = 1; i < maxPrime; ++i)
            if (isPrime(i))
                  *(pTable + (i / longSize)) += (1 << ((i % 32)));
      
      endTick = GetTickCount();
      cout << "Done building array, Time: " << (endTick - startTick) << "ms" << endl << endl;

      do
      {
            cout << endl << "Please enter a number to check between 1 - " << maxPrime << " (0 exits): " << endl;
            cin >> theNumber;
            if (theNumber > 0 && theNumber < maxPrime)
            {
                  isItPrime = 0;
                  int val;
                  val = *(pTable + (theNumber / longSize));
                  isItPrime = (val >> (theNumber % 32) & 1);
                  cout << theNumber << ((isItPrime == 1) ? (" is prime") : (" is not prime")) << endl;
            }
      } while (theNumber > 0 && theNumber < maxPrime);


      cout << endl << endl;
      system("PAUSE");

      delete []pTable;
}
0
 
LVL 84

Accepted Solution

by:
ozo earned 500 total points
ID: 17786683
malloc(numItems) should be malloc(numItems*sizeof(*pTable))
0
 
LVL 19

Author Comment

by:BrianGEFF719
ID: 17786751
>>malloc(numItems) should be malloc(numItems*sizeof(*pTable))

Thats right malloc takes a number of bytes. I was getting it confused with the new operator in C++.
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 17787404
>>>> I was getting it confused with the new operator in C++.

Why didn't you use the 'new' operator?

There is no advantage using malloc over new. Especially if you are not experienced malloc is a bad choice. if using C++ class or struct, malloc/free doesn't invoke constructor/destructor what will cause the next headache.

>>>> where the each bit was set corresponding to the number being prime
>>>> Make sense?

Using template class bitset would turn the prog to

#include <bitset>
#include <iostream>
using namespace std;

int main ()
{
     long theNumber,startTick,endTick;
     const size_t maxPrime = 1000000;
     bool isItPrime;
     bitset<maxPrime> primeBits;

     cout << "Building bitset...";
     startTick = GetTickCount();
     
     long l;
     primeBits.reset();

     for (l = 0 ; l < maxPrime; ++l )
     {
         if (isPrime(++l))
         {
            primeBits.set(l, true);
         }
     }
     
     endTick = GetTickCount();
     cout << "Done building array, Time: " << (endTick - startTick) << "ms" << endl << endl;

     do
     {
          cout << endl << "Please enter a number to check between 1 - " << maxPrime << " (0 exits): " << endl;
          cin >> theNumber;
          if (theNumber > 2 && theNumber < maxPrime)
          {
               isItPrime = primeBits[theNumber];

               cout << theNumber << ((isItPrime) ? (" is prime") : (" is not prime")) << endl;
          }
     } while (theNumber > 0 && theNumber < maxPrime);

     cout << endl << endl;
     system("PAUSE");

     return 0;
}




Regards, Alex



0

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Suggested Solutions

This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
The goal of this video is to provide viewers with basic examples to understand how to use strings and some functions related to them in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.

744 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

11 Experts available now in Live!

Get 1:1 Help Now