# Jackey's 感悟

Do Research

```// finds the primes between 2 and n; uses the Sieve of Eratosthenes,
// deleting all multiples of 2, all multiples of 3, all multiples of 5,
// etc.; not efficient, e.g. each thread should do deleting for a whole
// block of values of base before going to nextbase for more

// usage:  sieve nthreads n
// where nthreads is the number of worker threads

#include <stdio.h>
#include <math.h>

#define MAX_N 100000000

// shared variables
int nthreads,  // number of threads (not counting main())
n,  // upper bound of range in which to find primes
prime[MAX_N+1],  // in the end, prime[i] = 1 if i prime, else 0
nextbase;  // next sieve multiplier to be used

int work[MAX_THREADS];  // to measure how much work each thread does,
// in terms of number of sieve multipliers checked

// lock index for the shared variable nextbase

// ID structs for the threads

// "crosses out" all multiples of k, from k*k on
void crossout(int k)
{  int i;

for (i = k; i*k <= n; i++)  {
prime[i*k] = 0;
}
}

// worker thread routine
void *worker(int tn)  // tn is the thread number (0,1,...)
{  int lim,base;

// no need to check multipliers bigger than sqrt(n)
lim = sqrt(n);

do  {
// get next sieve multiplier, avoiding duplication across threads
base = nextbase += 2;
if (base <= lim)  {
work[tn]++;  // log work done by this thread
// don't bother with crossing out if base is known to be
// composite
if (prime[base])
crossout(base);
}
else return;
} while (1);
}

main(int argc, char **argv)
{  int nprimes,  // number of primes found
totwork,  // number of base values checked
i;
void *p;

n = atoi(argv);
for (i = 2; i <= n; i++)
prime[i] = 1;
crossout(2);
nextbase = 1;
// get threads started
for (i = 0; i < nthreads; i++)  {
pthread_create(&id[i],NULL,(void *) worker,(void *) i);
}

// wait for all done
totwork = 0;
for (i = 0; i < nthreads; i++)  {
printf("%d values of base done\n",work[i]);
totwork += work[i];
}
printf("%d total values of base done\n",totwork);

// report results
nprimes = 0;
for (i = 2; i <= n; i++)
if (prime[i]) nprimes++;
printf("the number of primes found was %d\n",nprimes);

}
// finds the primes between 2 and n; uses the Sieve of Eratosthenes,
// deleting all multiples of 2, all multiples of 3, all multiples of 5,
// etc.; not efficient, e.g. each thread should do deleting for a whole
// block of values of base before going to nextbase for more

// usage:  sieve nthreads n
// where nthreads is the number of worker threads

#include <stdio.h>
#include <math.h>

#define MAX_N 100000000

// shared variables
int nthreads,  // number of threads (not counting main())
n,  // upper bound of range in which to find primes
prime[MAX_N+1],  // in the end, prime[i] = 1 if i prime, else 0
nextbase;  // next sieve multiplier to be used

int work[MAX_THREADS];  // to measure how much work each thread does,
// in terms of number of sieve multipliers checked

// lock index for the shared variable nextbase

// ID structs for the threads

// "crosses out" all multiples of k, from k*k on
void crossout(int k)
{  int i;

for (i = k; i*k <= n; i++)  {
prime[i*k] = 0;
}
}

// worker thread routine
void *worker(int tn)  // tn is the thread number (0,1,...)
{  int lim,base;

// no need to check multipliers bigger than sqrt(n)
lim = sqrt(n);

do  {
// get next sieve multiplier, avoiding duplication across threads
base = nextbase += 2;
if (base <= lim)  {
work[tn]++;  // log work done by this thread
// don't bother with crossing out if base is known to be
// composite
if (prime[base])
crossout(base);
}
else return;
} while (1);
}

main(int argc, char **argv)
{  int nprimes,  // number of primes found
totwork,  // number of base values checked
i;
void *p;

n = atoi(argv);
for (i = 2; i <= n; i++)
prime[i] = 1;
crossout(2);
nextbase = 1;
// get threads started
for (i = 0; i < nthreads; i++)  {
pthread_create(&id[i],NULL,(void *) worker,(void *) i);
}

// wait for all done
totwork = 0;
for (i = 0; i < nthreads; i++)  {
printf("%d values of base done\n",work[i]);
totwork += work[i];
}
printf("%d total values of base done\n",totwork);

// report results
nprimes = 0;
for (i = 2; i <= n; i++)
if (prime[i]) nprimes++;
printf("the number of primes found was %d\n",nprimes);

}

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5d868196e6a29', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5d868196e6a6b',  {
collapseEmpty: 'before',
sectionId: '26942',
location: 120,
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5d868196e6a73',  {
collapseEmpty: 'before',
sectionId: '114160',
location: 130,
width: 300,
height: 250
});
});