Fun with prime numbers!

[Caffiend]

Thanks to everyone who helped me out with my early version of the prime number calculator... Here is the complete and updated version including unsigned 64 bit integers...mmmm mm....... Lots of fun with the higher numbers, but my humble 1.86 gHz centrino with 1gb RAM slows to a crawl with numbers in excess of a billion or ten.... :-) Here is the complete program, if you want to have some fun with it:

#include <iostream>
#include <math.h>
using namespace std;

unsigned __int64 knum;
unsigned __int64 i = 1;
unsigned __int64 pt = 0;
bool is_prime;


int main() 
{
  cout << endl << endl;
  cout << "This Program calulates the prime numbers between" << endl;
  cout << "a given start and end number.";  
  start: cout << endl << endl << "Please enter a starting number (enter 0 to exit): ";
  cin >> i;
  if (i == 0)
  goto close;
  cout << endl << "Please enter an ending number: ";
  cin >> knum;  
  cout << endl << endl;  
  cin.get();
  
  while ((i <= knum) && (i > 0)) 
  {
      is_prime = true;
      for (pt = 2; pt <= sqrt(i); pt++) // all numbers are divided by 1 so start from 2
      {
        if (i % pt == 0)
          is_prime = false;
      }// only when the "for" cycle is done we know for sure if "i" is prime
      if (is_prime)
        cout << i << ", ";
      i++;   
  }
goto start;

close: cin.get();
  return 0;
}

Let me know what you think, or if you have any suggestions for improvements (other than graphics ;-P)

[Ganon11]

Improvement number 1:

Get rid of goto statements.

You can use a while loop to continue executing until i == 0 instead.

[Caffiend]

Done, used a while loop over the code formerly covered by the gotos, then put in a break if i == 0. Out of curiosity, what is wrong with goto statements?

[Ganon11]

I'm not sure if the 'official' world of programming dislikes them, but I've heard they can get incredibly messy and are considered unprofessional. I know my teacher's favorite saying is something like, "God kills a kitten every time you type 'goto'."

[Banfa]

I would say that you should only use a goto if

a) You are already an expert C/C++ programmer
b) It is really necessary
c) It is really necessary

Now I realise that, technically speaking, that's only 2 conditions but I thought the second one was such a big one it was worth mentioning twice.



Onto your prime number algorithm

You can seriously speed up you search by not checking every number, in fact you only have to check lower numbered primes so all you have to do is keep a record of them (OK this method does take rather a lot more memory).

For instance in you algorithm if you what to check if 53 is prime you see if it is divisible by

2, 3, 4, 5, 6, 7 (you stop at the square root of 53 which is 7)

However you only need to check

2, 3, 5, 7

4 is 2x2 so if it is divisible by 4 it is divisible by 2 and not a prime so you don't need to check 4

6 which is 2x3 does not need to be checked for a similar reason.

Now for such a low number the saving is not great but with bigger numbers the saving in itterations and calculations is huge.