## prime generator using bitmap

Write here if you have problems with your C++ source code

Moderator: Board moderators

### prime generator using bitmap

I tried to generate a prime generator using bitmap. Here is the reference:
http://www.algorithmist.com/index.php/Prime_Sieve_of_Eratosthenes.c
But I failed. My program generates wrong number of primes.

I efforted to find out the missing primes, and I got two values: 203897 and 643649.
This two values are unusual and I have no idea about it.

Sincerely,
Please help correct the code.

Code: Select all
`#include <iostream>#include <vector>using namespace std;   unsigned sieve[1000000/64+1];   vector<int> v1;void make_prime() {   v1.push_back(2);   register unsigned i, j, k;   for (i = 1; i < 1000000/2; i++) {      if (((sieve[i>>5]>>(i&31))&1)==0) {         for (j=(i+1)*i*2, k=2*i+1; j < 1000000/2; j+=k)            sieve[j>>5] |= 1<<(j&31);         v1.push_back(i*2+1);      }   }}   bool sieve2[1000000];   vector<int> v2;void make_prime2() {   for (int p=0;p<1000000;p++) sieve2[p]=true;   for (int i=2;i<1000000;i++)      if (sieve2[i]) {         for (int j=i+i;j<1000000;j+=i)            sieve2[j]=false;         v2.push_back(i);      }}int main() {   make_prime();   make_prime2();   cout << "size of v1 = " << v1.size() << endl;   cout << "size of v2 = " << v2.size() << endl;   // the missing prime are 203897 and 643649   for (int i=0;i<v2.size();i++) {      if (v2[i] == 203897) cout << "find 203897 at position " << i << endl;      if (v2[i] == 643649) cout << "find 643649 at position " << i << endl;   }   return 0;}`

--
DJWS, a newbie in programming
DJWS
Learning poster

Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan

You modified the code, and it caused integer overflow. Try this version of make_prime():
Code: Select all
`void make_prime() {   v1.push_back(2);   register unsigned i, j, k;   for (i = 1; i < 1000000/2; i++) {      if (((sieve[i>>5]>>(i&31))&1)==0) {         if (i < 500) {    /* 500 = sqrt(1000000)/2 */            for (j=(i+1)*i*2, k=2*i+1; j < 1000000/2; j+=k)               sieve[j>>5] |= 1<<(j&31);         }         v1.push_back(i*2+1);      }   }}`
mf
Guru

Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland

Sharp eyes!
Thank you

PS: bitmap approach is truly efficient
--
DJWS, a newbie in programming
DJWS
Learning poster

Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan

### Re: prime generator using bitmap

How do you change massive amounts of BITMAP images to JPEG images? I have folders of scanned photos in Bitmap format that I want to change to Jpeg images at one time. What is a good program to use for this?
_____________________________________
yahoo keyword tool ~ overture ~ traffic estimator ~ adwords traffic estimator
edeferaxy
New poster

Posts: 2
Joined: Fri Jan 20, 2012 8:23 am

Return to C++

### Who is online

Users browsing this forum: No registered users and 0 guests