prime generator using bitmap

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

Moderator: Board moderators

Post Reply
DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

prime generator using bitmap

Post by DJWS » Sun Apr 09, 2006 4:12 pm

I tried to generate a prime generator using bitmap. Here is the reference:
http://www.algorithmist.com/index.php/P ... osthenes.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 :wink:

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

Post by mf » Sun Apr 09, 2006 4:53 pm

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);
      }
   }
}

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

Post by DJWS » Sun Apr 09, 2006 6:05 pm

Sharp eyes!
Thank you :)

PS: bitmap approach is truly efficient :P
--
DJWS, a newbie in programming :wink:

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

Re: prime generator using bitmap

Post by edeferaxy » Fri Jan 20, 2012 12:48 pm

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

Post Reply

Return to “C++”