[C++] Tutorial: How to calculate primenumbers!?

[Daevius]

Hi,

Inspired by Kyle Enos's great 2 tutorial threads, I thought about making a tutorial too . About calculating prime numbers.

Requirements:
- Compiler (IDE is advised)

Program goal:
- Calculate primenumbers
- Print them on screen
- Stop if the max is reached (max is entered by user on start) or when a key got hit
- Display number of milliseconds the script took to complete the calculations

Okay, lets start:

Calculate primenumbers:
So how do we calculate them? First a few facts about primenumbers. A primenumber is a number that can only be divided by 1 or itself (to get a round number). That means that 7 is a primenumber, but 9 (3x3) isn't! This also means that every even number is not a primenumber, except 2.

Conclusion: we shouldn't check all numbers to calculate if its a primenumber or not. We should only check the odd numbers, except for 2. So if we print 1 and 2 as primenumbers manually on screen, we can start with checking the number 3 for being prime or not. Than we keep increasing the currently checked number for being prime by 2. We start with 3, than 5, 7, 9, 11 etc.

3 is the first number we start with. If its prime, we can only divide it by 1 and 3, and not by 2. If we divide it by 2, we get 1.5, so its a primenumber! Same for 5, 7 and 11.

So how do we write that in C++? For example we check 11. We start by calculating 11/2, than 11/3. Both don't result in round numbers. So its a prime number...but hey, we only calculated till 11/3, so we forgot to calculate 11/4, 11/5, 11/6, 11/7, 11/8, 11/9, 11/10 you might think. But we only have to divide it till the squareroot of 11 or below. I will explain this with the number 16, as thats easier:

16 is not a prime number: (1x16 and 16x1 are not listed, as thats true for every number)
2x8 = 16
4x4 = 16
8x2 = 16

Notice that 2x8 and 8x2 are exactly the same except for the sequence. So in fact we only have to check for 2x8 and 4x4 (4 is the squareroot of 16).

Another thing: for 11, we only have to check for 11/3 and not for 11/2. Because every number we test for being prime or not, is an odd number, so it will never result in a round number if we divide it by an even number. Therefore the number with which we divide should start with 3 and should increase with 2 each time (3, 5, 7, 9, 11).

int i = 3, o;

    while (i)
    {
        o = 3;
        while (o <= sqrt(i))
        {
            if (i % o == 0)
            {
               break;
            }
            o += 2;
        }
        i += 2;
    }

We start by checking 3 for being prime or not. To check if its prime, we start by dividing it by 3. We keep increasing 'o' by 2, as long as it is smaller or equal to the square root of 3. The square root of 3 is 1.7, so we don't go through the inner while loop at all. 3 is a primenumber.

Same for 5 and 7.

Than we calculate it for 11. The square root of 11 is 3.3, so we loop once through the inner while loop. The percentage character (%) returns the remainder if you divide the first by the second argument. 5%2 = 1, 8%2 = 0, 11%3 = 2. So 11%3 does not equals 0, so we don't stop the loop because its not a prime, but we continue and increase 3 by 2 = 5. 5 is bigger than the square root of 11, so we _do_ quit the loop, lol, and its a prime.

So that way we can search for prime numbers

Print them on screen
We use the cout function for this, and the needed headers and stuff:

#include <iostream>
#include <math.h>

using namespace std;

int main()
{
    int i = 3, o;
    bool prime;

    cout << "\n1\n2\n";
    while (i)
    {
        prime = true;
        o = 3;
        while (o <= sqrt(i))
        {
            if (i % o == 0)
            {
               prime = false;
               break;
            }
            o += 2;
        }

        if (prime)
        {
            cout << i << "\n";
        }
        i += 2;
    }
    return 0;
}

Here we add the boolean 'prime' to see if its a primenumber, because we only want primenumbers to be printed on the screen. We also print the numbers 1 and 2 manually as described above.

Stop if the max is reached (max is entered by user on start) or when a key got hit
To get user input, we use the cin function. And to know if a key gets hit, we use the kbhit(); function (conio.h header).

#include <iostream>
#include <math.h>
#include <conio.h>

using namespace std;

int main()
{
    int i = 3, o, max;
    bool prime;

    cout << "Maximal: ";
    cin >> max;

    cout << "\n1\n2\n";
    while (i <= max)
    {
        prime = true;
        o = 3;
        while (o <= sqrt(i))
        {
            if (i % o == 0)
            {
               prime = false;
               break;
            }
            o += 2;
        }

        if (prime)
        {
            cout << i << "\n";
        }

        if (kbhit())
        {
            break;
        }
        i += 2;
    }
    return 0;
}

The entered number 'max' will be the maximal number 'i' can get. Except if a key gets hit, it will quit the while loop earlier.

Display number of milliseconds the script took to complete the calculations
Here we use the clock(); function, to get the time in milliseconds. So before we output it, we need to divide it by 1000 to display it as seconds. However, we only calculate the time passed by the actual primenumber calculations, and not the time the user took to enter the desired max (clock() gives the number of milliseconds passed since the start of the application).

#include <iostream>
#include <math.h>
#include <conio.h>

using namespace std;

int main()
{
    int i = 3, o, max;
    bool prime;
    double seconds;

    cout << "Maximal: ";
    cin >> max;

    cout << "\n1\n2\n";
    seconds = clock();
    while (i <= max)
    {
        prime = true;
        o = 3;
        while (o <= sqrt(i))
        {
            if (i % o == 0)
            {
               prime = false;
               break;
            }
            o += 2;
        }

        if (prime)
        {
            cout << i << "\n";
        }

        if (kbhit())
        {
            break;
        }
        i += 2;
    }
    seconds = clock() - seconds;
    cout << "\n" << seconds / 1000 << " seconds" << endl;
    return 0;
}

Final code:
We want the application to pause before closing, so the user can actually see the number of passed seconds. The system("PAUSE"); function can be used for this, but remember that this is windows only!

Final code for windows (other platforms should just delete the system("PAUSE"); line at the end):
Source code
Executable + Source code (zip)

I hope you understand the theory. If you have any questions, suggestions or improvements, feel free to reply .

Daevius

PS: To keep the script going without a max, just enter something else than a number .
PSS: Script update. 'o' now starts with 3 and gets increased by 2. Thanks to _Gabriel_.

 

[Loregoreth]

Very cool, You should make one about Classes and OOP.

 

[_Gabriel_]

First of all, I would like to congratulate you. Nice job. :smile:

I have also written one in a few minutes to print the first 'i' prime numbers.

#include <stdio.h>
#include <conio.h>

int i,nr;

int prime(int x)
  {
   if(x==1)
     return 0;
   if(x%2==0&&x!=2)
     return 0;
   for(int d=3; d*d<=x; d+=2)
     if(x%d==0) 
       return 0;
   return 1;
  }

void main()
  {
   clrscr();
   printf("Enter your value: "); scanf(%d,&i)
   for(int j=1; j<=32767; j+=2)
     {
      if(prime(j)&&nr<=i)
        {
         printf("%d ",i);
         nr++;
        }
      if(nr>i)
        break;
     }
   getch();
  }

I don't know if you understand it, but I believe it can be executed faster.

I have only used Notepad, so if there are any errors, I am sorry.

 

[Absolute]

Nice Job Mate. Thank You

 

[Daevius]

Thanks for the reactions

First of all, I would like to congratulate you. Nice job. :smile:

I have also written one in a few minutes to print the first 'i' prime numbers.

#include <stdio.h>
#include <conio.h>

int i,nr;

int prime(int x)
  {
   if(x==1)
     return 0;
   if(x%2==0&&x!=2)
     return 0;
   for(int d=3; d*d<=x; d+=2)
     if(x%d==0) 
       return 0;
   return 1;
  }

void main()
  {
   clrscr();
   printf("Enter your value: "); scanf(%d,&i)
   for(int j=1; j<=32767; j+=2)
     {
      if(prime(j)&&nr<=i)
        {
         printf("%d ",i);
         nr++;
        }
      if(nr>i)
        break;
     }
   getch();
  }

I don't know if you understand it, but I believe it can be executed faster.

I have only used Notepad, so if there are any errors, I am sorry.

Looks nice, you just do the same but a bit different. Except for the prime checking part:

for(int d=3; d*d<=x; d+=2)
     if(x%d==0) 
       return 0;

Yes, increasing by 2 is faster indeed, I might change that in the tutorial .

EDIT:
Changed, thanks , it took m first 1.13 seconds till 100,000, now only 0.93 . After some optimization flags in the compiler I managed to get it till 100,000 in 0.73 seconds!

@Loregoreth:
Maybe, but 'm not an expert in classes in C, as I never made any big project

 

[GriffinHeart]

now do a tutorial how to factorize prime numbers in an efecient way xP

anyways good toturial but very slow execution times, seriously prime numbers are a big issue in security this days so theres loads of stuff around for them

 

[Daevius]

If you get rid of the console output it gets to 2.8 to 4.9 seconds till 1m (instead of 7.8 for 1m in the updated version above), I'm working on a ASM square root function, which might be faster...

PS: I can even make it memory time tradeoff... that will make it 500x faster (my maths teacher did that)

 

[ghell]

The above implementations are incredibly slow (yes, 2.8 seconds counts as incredibly slow when the function actually needs to be used in something). The following sieve runs in O time [according to wikipedia] for finding all primes up to a limit (not so good for finding out if a specific number is prime, there are other algorithms for that). There are other efficient algorithms but they are much more complicated and I was too lazy to port them to C. It was hard enough to find something that could display this algorithm's running time as more than 0, even when run multiple times.

#include <stdio.h>
#include <time.h>

int eratosthenes(unsigned int limit)
{
  if(limit < 2)
    return 1;
  
  char primes[limit];
  int i, j;
  
  /* Assume each number is prime */
  for(i = 2; i < limit; i++)
    primes[i] = 1;
  
  for(i = 2; i < limit; i++)
  {
  	/* If the number is a prime mark its multiples as non prime */
  	if(primes[i] == 1)
  	{
  	  //printf("%d ", i);
  	  for(j = i*i; j < limit; j += i)
  	    primes[j] = 0;
  	}
  }
  
  return 0;
}

int main(int argc, char* argv[])
{
  clock_t start, end;
  int limit = 1000000;
  double delta_seconds;
  
  start = clock();
  eratosthenes(limit);
  end = clock();
  
  delta_seconds = (double)(end - start) / CLOCKS_PER_SEC;
  
  printf("%d limit calculated in %f seconds.\n", limit, delta_seconds);

  return 0;
}

Output on a Core 2 Duo E6600:

1000000 limit calculated in 0.005000 seconds

This timer is not completely accurate but it was as good as I could find.

This was compiled with mingw's default settings, no optimisation flags etc. Adding -O3 makes it faster for example.

 

[_Gabriel_]

I don't think that using 2 for function is faster. :-?

 

[Daevius]

The above implementations are incredibly slow (yes, 2.8 seconds counts as incredibly slow when the function actually needs to be used in something). The following sieve runs in O time [according to wikipedia] for finding all primes up to a limit (not so good for finding out if a specific number is prime, there are other algorithms for that). There are other efficient algorithms but they are much more complicated and I was too lazy to port them to C. It was hard enough to find something that could display this algorithm's running time as more than 0, even when run multiple times.

#include <stdio.h>
#include <time.h>

int eratosthenes(unsigned int limit)
{
  if(limit < 2)
    return 1;
  
  char primes[limit];
  int i, j;
  
  /* Assume each number is prime */
  for(i = 2; i < limit; i++)
    primes[i] = 1;
  
  for(i = 2; i < limit; i++)
  {
      /* If the number is a prime mark its multiples as non prime */
      if(primes[i] == 1)
      {
        //printf("%d ", i);
        for(j = i*i; j < limit; j += i)
          primes[j] = 0;
      }
  }
  
  return 0;
}

int main(int argc, char* argv[])
{
  clock_t start, end;
  int limit = 1000000;
  double delta_seconds;
  
  start = clock();
  eratosthenes(limit);
  end = clock();
  
  delta_seconds = (double)(end - start) / CLOCKS_PER_SEC;
  
  printf("%d limit calculated in %f seconds.\n", limit, delta_seconds);

  return 0;
}

Output on a Core 2 Duo E6600:

1000000 limit calculated in 0.005000 seconds

This timer is not completely accurate but it was as good as I could find.

This was compiled with mingw's default settings, no optimisation flags etc. Adding -O3 makes it faster for example.

Cool, with printing in console it takes 1.4s for 1m , so thats 5.5 times faster .
Thanks , I will investigate

 

[ghell]

If you really need the output printed, try printing to the console and redirecting the output to a file to minimise the effect of printing it (the program still prints it but your CPU isn't busy drawing it to the screen, scrolling the console etc while the algorithm runs) like this:
prime.exe > primes.txt

The algorithm is actually a lot more than 5.5 times faster but the higher the limit the better the effect. Unfortunately to get much more than a million you need to use the heap and pointer arithmetic etc. (also remembering that a byte is the smallest unit you can store in memory so a limit of 1 million with this sieve takes about 1 megabyte of memory. This can be cut to an eighth of this by using bit shifting but that slightly increases the number of operations in the algorithm and makes it harder to see how the algorithm works.)

The console output will be misleading anyway as the I/O time to print it to console vastly outweighs the running time of the algorithm. It would be better to compare the 2 running times with no output to console. You mentioned 2.8s as the best running time with no output to the console, compared to my 0.005000s (not 100% accurate but it is very hard to measure time accurately over a short period of time) this is ~560 times faster on an input of 1 million. There are a lot of variables in here that make it harder to measure such as which CPU you are running it on, if the compiler optimised it, the process priority etc.

This is because your algorithm runs in O(n^2) but the Eratosthenes sieve runs in O. So if you have a limit of 10, O(n^2) will take 100 operations, O will take 10. If you have a limit of 1,000,000 O(n^2) will take 1,000,000,000,000 operations but O will take 1,000,000. (If you aren't familiar with O notation, this isn't an accurate number of operations, it only includes the most significant order)

The advantage comes on very large input size. Some problems are so large or so complex that it would take hundreds of years to solve them today if you used every computer in the world to help solve them. (they usually have a number of operations around the order of the number of atoms in the universe). One example of a large problem is TSP where a simple algorithm such as listing all the possible routes and then picking the best one sounds fine until you realise how long it will take for just 50 nodes (I think the original problem was to visit all 50 US states or something). Some of these problems also have large cash prizes for solving them.

If you need 100% accurate results (such as in listing the prime numbers to a limit) it is ideal to get a running time of O(log n) or better. (this means when you double the input size, it only takes 1 more operation to complete.. tree structures are useful for this). If you can live with a pretty good approximation (such as TSP, do you really NEED to find the best route or will a route that is 95% as good be OK) then you can probably use AI instead. (I think an AI approach to solve TSP is to connect all the nodes then switch lines that cross until no lines cross)

 

[Daevius]

If you really need the output printed, try printing to the console and redirecting the output to a file to minimise the effect of printing it (the program still prints it but your CPU isn't busy drawing it to the screen, scrolling the console etc while the algorithm runs) like this:
prime.exe > primes.txt

The algorithm is actually a lot more than 5.5 times faster but the higher the limit the better the effect. Unfortunately to get much more than a million you need to use the heap and pointer arithmetic etc. (also remembering that a byte is the smallest unit you can store in memory so a limit of 1 million with this sieve takes about 1 megabyte of memory. This can be cut to an eighth of this by using bit shifting but that slightly increases the number of operations in the algorithm and makes it harder to see how the algorithm works.)

The console output will be misleading anyway as the I/O time to print it to console vastly outweighs the running time of the algorithm. It would be better to compare the 2 running times with no output to console. You mentioned 2.8s as the best running time with no output to the console, compared to my 0.005000s (not 100% accurate but it is very hard to measure time accurately over a short period of time) this is ~560 times faster on an input of 1 million. There are a lot of variables in here that make it harder to measure such as which CPU you are running it on, if the compiler optimised it, the process priority etc.

This is because your algorithm runs in O(n^2) but the Eratosthenes sieve runs in O. So if you have a limit of 10, O(n^2) will take 100 operations, O will take 10. If you have a limit of 1,000,000 O(n^2) will take 1,000,000,000,000 operations but O will take 1,000,000. (If you aren't familiar with O notation, this isn't an accurate number of operations, it only includes the most significant order)

The advantage comes on very large input size. Some problems are so large or so complex that it would take hundreds of years to solve them today if you used every computer in the world to help solve them. (they usually have a number of operations around the order of the number of atoms in the universe). One example of a large problem is TSP where a simple algorithm such as listing all the possible routes and then picking the best one sounds fine until you realise how long it will take for just 50 nodes (I think the original problem was to visit all 50 US states or something). Some of these problems also have large cash prizes for solving them.

If you need 100% accurate results (such as in listing the prime numbers to a limit) it is ideal to get a running time of O(log n) or better. (this means when you double the input size, it only takes 1 more operation to complete.. tree structures are useful for this). If you can live with a pretty good approximation (such as TSP, do you really NEED to find the best route or will a route that is 95% as good be OK) then you can probably use AI instead. (I think an AI approach to solve TSP is to connect all the nodes then switch lines that cross until no lines cross)

Thanks for the explaination .

And yes, as I mentioned, memory tradeoff would make it 500x faster, seemed to be 560x till a million. But my method won't require as much memory as the script you provided does. But the eratosthenes method is exactly what my teacher mentioned .

Isn't it impossible to make it O(log n)?

PS: With O(log n) you will get one more operation if the size increases by 10, not by 2

 

[ghell]

In computer science log is assumed to the base 2 not 10, hence doubled not multiplied by 10

Calculating all prime numbers to a limit has not (yet) been done in O(log n) time AFAIK. The sieve of Atkin is one more complicated algorithm that runs in O(n/log log n) time (so it is getting towards O(log n) but not quite there)

Though sieves use more memory than your algorithm, it is not technically a time-memory tradeoff (I think). Other data structures than an array could have been used to lower memory usage (or the array's size could have been halved because you already know all even numbers except 2 are non-prime etc) but an array was simplest and provides random access to its elements (look up of an element is constant time O(1)). It just uses more memory to remember previous results than to recalculate it every time