perfect.c

/* perfect.c: find all perfect numbers up to a bound */

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <pthread.h>
#include <assert.h>

int num_perfect_global = 0;   // global number of perfect numbers
int * local_perfects;         // local total of perfect nums
int bound;                    // upper bound of search
int nthreads;                 // number of threads to use

double mytime() {
  struct timeval t;
  gettimeofday(&t, NULL);
  return t.tv_sec + t.tv_usec/1000000.0;
}

_Bool is_perfect(int n) {
  if (n < 2) return 0;
  int sum = 1, i = 2;
  while (1) {
    const int i_squared = i*i;
    if (i_squared < n) {
      if (n%i == 0) sum += i + n/i;
      i++;
    } else {
      if (i_squared == n) sum += i;
      break;
    }
  }
  return sum == n;
}


void * thread_f(void * arg) {
  int * tid = (int *) arg;
  int local_perfect_numbers = 0;
  for (int i = *tid; i <= bound; i += nthreads)
  {
    if (i%1000000 == 0) {
      printf("i = %d\n", i);
      fflush(stdout);
    }
    if (is_perfect(i)) {
      printf("Found a perfect number: %d\n", i);
      local_perfect_numbers++;
    }
  }
  local_perfects[*tid] += local_perfect_numbers;
  return NULL;
}

int main(int argc, char * argv[]) {
  int nthreads; // number of threads to created

  if (argc != 3) {
    printf("Usage: perfect.exec bound threads\n");
    exit(1);
  }
  bound = atoi(argv[1]);
  nthreads = atoi(argv[2]);
  assert(argc == 3);

  double start_time = mytime();
  local_perfects = malloc((nthreads+1)*sizeof(int));
  
  int tids[nthreads];
  pthread_t threads[nthreads];

  for (int i = 0; i < nthreads; i++)
        tids[i] = i;
  for (int i = 0; i < nthreads; i++)
        pthread_create(threads + i, NULL, thread_f, tids +i);
  for (int i = 0; i < nthreads; i++)
        pthread_join(threads[i], NULL);
  for (int i = 0; i < nthreads; i++)
    num_perfect_global+=local_perfects[i];

  printf("Number of perfect numbers less than or equal to %d: %d.  Time = %lf\n",
	 bound, num_perfect_global, mytime() - start_time);
}