Latest Articles Latest Articles

Apr 21, 2008 Powered By SQLite
Apr 20, 2008 Double-Time Blogs Are Back!
Sep 05, 2006 Finding Prime Numbers Using C++
Jul 01, 2006 Finding Prime Numbers - A Simple Assembly Language Example Using NASM

Finding Prime Numbers Using C++

Ever since I wrote Finding Prime Numbers: A Simple Assembly Language Example Using NASM I've noticed a steady stream of Google queries for "Find prime numbers using c/c++." Given that I'm giving myself a refresher in c++ (I'm a c# guy myself), I thought now would be a nice time to port the code to c++. Please read the original article if you don't understand some of the logic behind what's going on.

I'm assuming this is a fairly popular homework assignment... if its your homework PLEASE try it on your own first. Copying someone else's code isn't going to help you!

Note (4/20/2008): Same note as in the assembly version of this example... this is not an optimized algorithm (not even close). Here's a hint for a real performance boost: use sqrt (you need to figure out where to use it).
#include<iostream>
#include<string>
using namespace std;


void main()
{
	
	int max;
	cin>>max;

	if(max <= 0)
	{
		cout<<"Please enter a digit > 0\n";

	}
	int* primes;
	int primecount = 0;

	//allocate enough memory for primes
	primes = new int[((int)(max/2)) + 1];

	primes[0] = 2;
	primecount++;

	//count by 2s because evens cant be prime 
        //(except 2, which we give for "free")
	for(int p = 3; p <= max; p+=2)
	{
		//if a number is divisible by a prime, it is not prime
		for(int i = 0; i < primecount; i++)
		{
			if(p%primes[i]==0)
			{	
				break;

			}

			//if the we've passed the point in the list where a 
                        //prime is larger than half of our
			//prime candidate, we definately have a prime
			if( (primes[i]) > (p/2) )
			{
				primes[primecount++] = p; 
				goto nextcandidate;
			}

		}
nextcandidate: ;

	}
	
	

	//Display max prime
	cout<<primes[primecount-1]<<endl;

	delete [] primes;


	cin>>max;
}