• API
• FAQ
• Tools
• Trends
• Archive
daily pastebin goal
58%
SHARE
TWEET

prime-sieve.c

a guest Nov 27th, 2013 40 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. /*      The purpose of this program is to list the first N prime
2.         numbers on the standard output.  Uses the Sieve of
3.         Eratosthenes.
4.
5.         Written by Hal Canary, 2010
6.
7.         Compile with:
8.                 cc -o prime-sieve prime-sieve.c
9. */
10. #include <stdio.h>
11. #include <stdlib.h>
12. #include <math.h>
13.
14. /* These two macros allow addressing of a particular bit inside of a
15.    large unsigned char array. */
16. #define bit_is_true(ARRAY, INDEX) \
17.   (((ARRAY) [(INDEX)/8] >> ((INDEX) % 8)) & 1)
18. #define set_bit_true(ARRAY, INDEX) \
19.   ((ARRAY)[(INDEX) >> 3] |= (1 << ((INDEX) & 7)))
20. /* And for completeness */
21. #define set_bit_false(ARRAY, INDEX)                                     \
22.   ((ARRAY)[(INDEX) >> 3] &= ~(1 << ((INDEX) & 7)))
23.
24. int main(int argc, char *argv[]) {
25.   unsigned int maxprime = 0; /* the number of numbers to test for primeness. */
26.   unsigned int test;    /* the number currently being tested for primeness */
27.   unsigned int multiple;   /* a composite */
28.   unsigned char *isprimes;  /* array of primes we have found so far. */
29.   unsigned int numprimes = 0;   /* How many primes we have found. */
30.   if (argc == 2) {
31.     maxprime = atoi(argv[1]);
32.   }
33.   if (maxprime == 0) {
34.     fprintf(stderr,"Usage: primus MAXPRIME\n");
35.     exit(1);
36.   }
37.   int size = (maxprime/8)+1;
38.   isprimes = malloc(size * sizeof(*isprimes));
39.   if (isprimes == NULL) {
40.     fprintf(stderr,"Can't allocate enough memory for that sieve.\n");
41.     exit(1);
42.   }
43.   for (test = 0; test < size; test++) {
44.     isprimes[test] = 0; /* may be a prime. */
45.   }
46.   int x;
47.   for (test = 2; test <= maxprime; test++) {
48.     if (bit_is_true(isprimes, test)) /* test is composite */
49.       continue;
50.     printf("%i\n",test);
51.     numprimes++;
52.     /* test is a prime */
53.     for (multiple = (test * test); multiple <= maxprime; multiple += test)
54.       set_bit_true(isprimes, multiple);
55.   }
56.   fprintf(stderr,"Between 2 and %i there are %i primes.\n",
57.           maxprime, numprimes);
58.   return 0;
59. }
RAW Paste Data
Top