Today, I'll give you a simple and practical example of using OpenMP with gcc. What's OpenMP? It's a C/C++/Fortran library for writing multithreaded applications. What's that? Most computers these days have multiple cores so that multiple tasks can be done in parallel. With multiple cores, you can edit pictures and listen to music at the same time without a noticeable slowdown. The intensive editing computations and music decoding happen on separate cores. It's a little more complicated than that, but that's the basic idea.

If your computer has multiple cores, it can use them in a single program. That's where OpenMP comes in. For concreteness, let's say you want to test whether the number 770948605618065977 is prime. If you're sane you'd just use the Miller-Rabin test like we've been discussing on this blog, and be happy with a 99.99999% probability that the number is prime. However, let's say you want to prove this number prime by trying all the numbers up to the integer part of its square root, which is 878036790.

Here is a minimal C program to do this:

More »