Skip to content

Instantly share code, notes, and snippets.

@muayyad-alsadi
Last active August 29, 2015 14:03
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save muayyad-alsadi/e0086560f796240548da to your computer and use it in GitHub Desktop.
Save muayyad-alsadi/e0086560f796240548da to your computer and use it in GitHub Desktop.
primes in C/C++
#include <stdlib.h>
#include <alloca.h>
#include <stdio.h>
#include <sys/time.h>
int* get_primes(int n, int *l) {
char* compo=(char*)alloca(n);
int* primes=(int*)malloc(sizeof(int)*n);
int i,j,c=0;
for(i=0;i<n;++i) compo[i]=0;
for(i=2;i<n;++i) {
if (compo[i]) continue;
primes[c++]=i;
for(j=i*2;j<n;j+=i) compo[j]=1;
}
*l=c;
return primes;
}
int main() {
struct timeval timer[2];
int i, l;
double dt;
int *primes=get_primes(100, &l);
/*
printf("we have %d primes: ", l);
for(i=0;i<l;++i) printf("%d ", primes[i]);
printf("\n");
*/
gettimeofday(&timer[0], NULL);
for(i=0;i<500;++i) get_primes(10000, &l);
gettimeofday(&timer[1], NULL);
printf("t0: %d %d\n", timer[0].tv_sec, timer[0].tv_usec);
printf("t1: %d %d\n", timer[1].tv_sec, timer[1].tv_usec);
dt=timer[1].tv_sec + timer[1].tv_usec/1000000.0;
dt-=timer[0].tv_sec + timer[0].tv_usec/1000000.0;
printf("dt=%g\n", dt);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment