The Old c++ Prime Number

[bohling]

OK, first off I have figured out the prime number algorithm...I guess.

What I am needing help with, or wanting the answer to, is how to count how many primes are being displayed. To wit:

Enter a Number: 10

There are 4 Primes. The Primes are:
7 5 3 2

Do you want to continue (y/n)?

This is what I have so far

#include <iostream>
using namespace std;

int main()
{
	int x; // input
	int y; // divisor
	int z; // prime
	
	char key; // to continue or not

	cout << "This program will allow you to enter a number and will display all and how many prime numbers from that number to 0." << endl << endl;


do
{
	cout << "Please enter a number: ";
	cin >> x;

	cout << endl;
	// cout << "There are " << counter << " primes in that range." << endl;
	cout << "All primes in this range are:" << endl << endl;

	for (z=x; z>=2; z--)
	{
		bool primeNo = false;

	for (y=2; y<z; y++)
	{
	
		if (z % y == 0)
		{
			primeNo = true;
		}
	}
		if (primeNo == false)
		{
			
			cout << z << " ";
			
		}
	}

	cout << endl << endl;
	cout << "Continue (y/n)? ";
	cin >> key;
}

	while (key == 'y'||key == 'Y');
	cout << endl << endl;
	
	system("PAUSE");

	return 0;

}

Thanks for your help!

[ravenous]

Rather than printing the primes out as you find them, store them in a std::vector instead. So, instead of

if (primeNo == false)
{
   cout << z << " ";
}

you'd have:

if ( primeNo == false )
{
   primes.push_back( z );
}

Then, when you've found all the primes and you want to display them, you can just do

std::cout << "There were " << primes.size() << " primes:" << std::endl;

for ( int i = 0; i < primes.size(); ++i )
   std::cout << primes[i] << " ";

std::cout << std::endl;

[rubberman]

Research "Sieve of Eratosthenes" for better understanding of how to do this. There is a good Wikipedia article on it: http://en.wikipedia.org/wiki/Sieve_of_Erastosthenes

[LRRR]

Well, in my opinion you have to ways to do that. Either you utilize your memory and increase your application's speed, or you use less memory but then you will end up with more number crunching - thus getting the results back will take more time.( A lot more with big numbers. )

I prefer the the first one, similar what ravenous wrote. I would recommend you to read this wiki article about the Sieve of Eratosthenes. This is a different approach, it's very easy to understand, but it's simplicity makes it brilliant at the same time. It's a fun project to write. :)

One more thing, don't get too excited about prime numbers like I did back then, and don't try to write the most efficient prime-number-finder-generator-whatever program you want to write, because it's pretty pointless. First of all the prime numbers were already found, in the range of int, long int etc. Plus there are way more efficient mathematical formulas to find primes, than what common folk can come up with. You probably not going to invent a better one, I know I wouldn't, but maybe you're different. Oh, by the way the big guns use the Miller-Rabin test, you can look it up in wikipedia. Have fun with your project. :)

p.s.: It took me so long to write this post, rubberman already recommended the wiki article. Anyway I am just going to leave this post here.

[adityatandon]

Hehe.. the sieve of erasthones is nice, but its utilising the same thing i posted in an earlier post..!! That is, if your number is indivisible by the numbers below 10, then it is 90% a prime number !!

P.S - This stands true for all numbers that are odd multiples of prime numbers

Eg: 169 = 13 x 13 ( 13 is a prime, yet 169 is indivisible by numbers below 10)

[LRRR]

I don't know what you've posted, but it should work the same. You can make it faster if you only put odd numbers in the range, since only one even prime number exists(2).

Beginning:

2 3 4 5 6 7 8 9 10

First run : if ( p % 2 == 0 )..
Everything will be tested after 2, we are going forward.

*
2 3 4 5 6 7 8 9 10
2 3 0 5 0 7 0 9 0


Second run : if ( p % 3 == 0 )..
Everything will be tested after 3.

  *
2 3 0 5 0 7 0 9 0 
2 3 0 5 0 7 0 0 0


Everything will be tested after 5.

      *
2 3 0 5 0 7 0 0 0
2 3 0 5 0 7 0 0 0


Forth run ( 7 ), none left to test.

          *
2 3 0 5 0 7 0 0 0
2 3 0 5 0 7 0 0 0

2 3 5 7 they are all primes. This is how it should work.

@adityatandon Your number remained invisible, because in order get rid of the non-prime numbers you have to run the algorithm until the square root of the biggest number in your list is reached. So in your case to the square root of 169, which is 13.

[adityatandon]

Umm..nope... what u can do is while running, u store the prime numbers found in an array and keep checking whether the number is a multiple of any of the primes above 10!! Surely that'd decrease processing speed.. but its worth it !
Also, what u could try is.. to check whether a number is prime or not, the following code can be used :

#
#           // Include necessary headers
# 

int main()
{clrscr();
int n,flag=1,numbr;
cout<<"Enter the number to be checked ";
cin>>n;

for(int i=1;i<n/2;++i)
    { if(n%i==0)
        {flag=0;
         numbr=i;
         break;
        }
     }

if(flag==0)
cout<<"As "<<n<<" is divisible by "<<numbr<<"it is not a prime number";

if(flag==1)
cout<<n<<" is a prime number";

return 0;
}

But yes, this increases run time !!

[LRRR]

@adityatandon It is enough to check until the square root of the biggest number is reached sqrt( n ) instead of n / 2. The beauty of the Sieve of Eratosthenes, it sort itself out, you don't need to store, or do anything else, but there are many other ways to find prime numbers it's up to you, how you approach it.

[bohling]

Wow. Well, this got more complex than what I was thinking. I thank everyone for their input, this will definitely expand my knowledge and way of thinking re c++.

I thought an array or some counting function would work, but I am somewhat new to the language (and programming in general) and this shows me that the easiest solution is not always the easiest solution, in terms of a beginners knowledge.

Again, I thank everyone for their responses.