Finding prime numbers, elegantly

[dockleryxk]

So a friend of mine and I are students trying to find prime numbers as fast as possible, using as little memory as possible. We want to find a prime number with crazy amounts of digits, thousands, millions, whatever. This is the base code but we want to tweak it to knock out as many possibilities of prime numbers as possible with each iteration of the algorithm. I figured you guys would have some good ideas! Thanks!

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

int main()
{
int number, remainder;
int count = 0;
cout << "Please enter an ending value: ";
cin >> number;

for(int n = 1; n <= number; n++)
{
for(int r = 2; r <= sqrt(n); r++)
{
remainder = n%r;
if(remainder == 0){
count++;
};
};
if(count == 0)
{
cout << n << " is a prime number." << endl;
};
count = 0;
};
};

[codekiddy]

I don't know what is your query, but I'm confused with your code because I can't see a reason in using a SQRT ?


Here is the same code without SQRT:

void prime_num(int num)
{
	bool prime = true;
	for ( int i = 0; i <= num; i++) 
	{
		for ( int j = 2; j <= num; j++) 
		{
			if ( i != j && i % j == 0 ) 
			{
				prime = false;
				break;
			}
		}
	prime ? cout <<"Prime:"<< i << endl : prime = true;
	}
}

[dockleryxk]

codekiddy,

It is there to cap the program so we can test it easily. My friend and I have only taken one class dealing with C++ so far, and that's the way we knew how to do it! Thanks for the feedback!

[Athar]

You should use the Sieve of Eratosthenes. Use one bit per uneven number (by using a vector<bool>, for example).