title: OpenMP Parallel for-loop showing little performance increase
body: <p>I am in the process of learning how to use OpenMP in C, and as a HelloWorld exercise I am writing a  program to count primes.  I then parallelise this as follows:</p>
  
  <pre><code>int numprimes = 0;
  #pragma omp parallel for reduction (+:numprimes)
  for (i = 1; i &lt;= n; i++)
  {
      if (is_prime(i) == true)
          numprimes ++;
  }
  </code></pre>
  
  <p>I compile this code using <code>gcc -g -Wall -fopenmp -o primes primes.c -lm</code> (<code>-lm</code> for the <code>math.h</code> functions I am using).  Then I run this code on an <code>Intel® Core™2 Duo CPU E8400 @ 3.00GHz × 2</code>, and as expected, the performance is better than for a serial program.</p>
  
  <p>The problem, however, comes when I try to run this on a much more powerful machine. (I have also tried to manually set the number of threads to use with <code>num_threads</code>, but this did not change anything.)  Counting all the primes up to <code>10 000 000</code> gives me the following times (using <code>time</code>):</p>
  
  <p>8-core machine:</p>
  
  <pre><code>real    0m8.230s
  user    0m50.425s
  sys     0m0.004s
  </code></pre>
  
  <p>dual-core machine:   </p>
  
  <pre><code>real    0m10.846s
  user    0m17.233s
  sys     0m0.004s
  </code></pre>
  
  <p>And this pattern continues for counting more primes, the machine with more cores shows a slight performance increase, but not as much as I would expect for having so many more cores available.  (I would expect 4 times more cores to imply almost 4 times less running time?)</p>
  
  <p>Counting primes up to <code>50 000 000</code>:</p>
  
  <p>8-core machine:</p>
  
  <pre><code>real    1m29.056s
  user    8m11.695s
  sys     0m0.017s
  </code></pre>
  
  <p>dual-core machine:</p>
  
  <pre><code>real    1m51.119s
  user    2m50.519s
  sys     0m0.060s
  </code></pre>
  
  <p>If anyone can clarify this for me, it would be much appreciated.</p>
  
  <p><strong>EDIT</strong></p>
  
  <p>This is my prime-checking function.</p>
  
  <pre><code>static int is_prime(int n)
  {
    /* handle special cases */
    if      (n == 0) return 0;
    else if (n == 1) return 0;
    else if (n == 2) return 1;
  
    int i;
    for(i=2;i&lt;=(int)(sqrt((double) n));i++)
      if (n%i==0) return 0;
  
    return 1;
  }
  </code></pre>