clock

[2AoiNwbp]

Hi guys,

I took this piece of code from the reference and made some adjustments trying to find out the time needed to process a single calculus on my machine (Dual core 2.00GHz) and noticed something weird, so I suspect I'm doing something wrong...
As is my understanding, the time needed for the following code is roughly as of Nth squared because of the nested loops.
Thus, since I`m using clock() and CLOCKS_PER_SECONDS (1000) cause I don't know if there's any function more precise than this, I divide by n twice, which would be n squared.

/* clock example: frequency of primes */
#include <stdio.h>      /* printf */
#include <time.h>       /* clock_t, clock, CLOCKS_PER_SEC */
#include <math.h>       /* sqrt */
#include <iostream>     // for system

int frequency_of_primes (unsigned int n) {
  int i,j;
  int freq=n-1;
  for (i=2; i<=n; ++i) 
    for (j=(int)sqrt(i);j>1;--j) 
        if (i%j==0) 
            {--freq; break;}
  return freq;
}

int main ()
{
  clock_t t;
  int f;
  unsigned int num = 9999999;
  t = clock();
  printf ("Calculating...\n");
  f = frequency_of_primes (num);
  printf ("The number of primes lower than %d is: %d\n",num+1, f);
  t = clock() - t;
  printf ("It took me %d clicks (%f seconds).\n",t,((float)t)/CLOCKS_PER_SEC);
  printf("It took me %.15f seconds per item.\n", ((float)t)/CLOCKS_PER_SEC/num/num);
  
  system("pause");
  return 0;
}

The results are as follows:
For 1,000,000 numbers:

It takes 2.4 seconds to get the job done.
It takes approx. 2 (pico?)seconds for each item.
(this, of course, because of the division)

For 10,000,000 numbers:

It takes 75.6 seconds to accomplish the whole task.
It takes approx. .8 (pico?)seconds each item

I believe in the power of C++, but.. something must be defenitely wrong!
I would like you to help me understand:
1. which is the correct way of doing it??
2. why the difference in time for each item? (since the calculus is the same)Is it for an error in the calculation, or is it because of the use of cache memory?
Thanks

regards,
Alejandro

[Duthomhas]

You are using an n² algorithm to look for primes.

For a small n, the algorithm runs in short time.
For a large n, the algorithm takes exponentially longer (because it's n², an exponential function).

So, a linear average for the time to find all n is not correct.
The time to find a small n is small.
The time to find a large n is large.

Plot it and you'll get the time to find ns looks like the famous curve.
https://www.google.com/search?q=n+squared+graph&source=lnms&tbm=isch

[2AoiNwbp]

Thanks