fork(3) download 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <unistd.h>
  4. #include <sys/times.h>
  5.  
  6. static unsigned P[] = {
  7. 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
  8. 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
  9. 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233,
  10. 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
  11. 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419,
  12. 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503,
  13. 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607,
  14. 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701,
  15. };
  16.  
  17. static int P_COUNT = sizeof(P)/sizeof(*P);
  18.  
  19. unsigned compute_fast (unsigned n, int I);
  20.  
  21. unsigned compute_slow (unsigned n, int I) {
  22.     unsigned sum = 1;
  23.     unsigned x = n;
  24.     for (int i = I; i < P_COUNT; ++i) {
  25.         if (P[i] > x / P[i]) break;    /* remaining primes won't divide x */
  26.         if (x % P[i] == 0) {           /* P[i] is a divisor of n */
  27.             unsigned sub = P[i] + 1;   /* add in power of P[i] */
  28.             x /= P[i];                 /* reduce x by P[i] */
  29.             while (x % P[i] == 0) {    /* while P[i] still divides x */
  30.                 x /= P[i];             /* reduce x */
  31.                 sub = sub * P[i] + 1;  /* add by another power of P[i] */
  32.             }
  33.             sum *= sub;                /* product of sums */
  34.             return sum * compute_fast(x, i+1);
  35.         }
  36.     }
  37.     if (x > 1) sum *= x + 1;           /* if x > 1, then x is prime */
  38.     return sum;
  39. }
  40.  
  41. unsigned compute_fast (unsigned n, int I) {
  42.     static unsigned M[5000000 + 1];    /* memoization of results */
  43.     if (!M[n])
  44.         M[n] = compute_slow(n, I);
  45.     return M[n];
  46. }
  47.  
  48. unsigned compute (unsigned n) {
  49.     return compute_fast(n, 0) - n;
  50. }
  51.  
  52. int main () {
  53.     unsigned cases = 500000;
  54.     unsigned i;
  55.     unsigned *n;
  56.     unsigned *r;
  57.     struct tms beg;
  58.     struct tms end;
  59.  
  60.     n = malloc(cases * sizeof(*n));
  61.     for (i = 0; i < cases; ++i) {
  62.         n[i] = i + 1;
  63.     }
  64.     srand(1010101);
  65.     for (i = 0; i < cases; ++i) {
  66.         unsigned j = rand() % 500000;
  67.         unsigned x = n[i];
  68.         n[i] = n[j];
  69.         n[j] = x;
  70.     }
  71.     r = malloc(cases * sizeof(*r));
  72.     times(&beg);
  73.     for (i = 0; i < cases; ++i) {
  74.         r[n[i]-1] = compute(n[i]);
  75.     }
  76.     times(&end);
  77.     free(r);
  78.     free(n);
  79.     double x = 0;
  80.     x += end.tms_utime;
  81.     x += end.tms_stime;
  82.     x -= beg.tms_utime;
  83.     x -= beg.tms_stime;
  84.     printf("%f seconds\n", x / sysconf(_SC_CLK_TCK));
  85.     return 0;
  86. }
Success #stdin #stdout 0.31s 21784KB
comments (?)
stdin 
Standard input is empty
stdout 
0.280000 seconds
https://ideone.com/qaD9HU
language:
C99 (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!