Is a prime number?

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <string.h>
  4
  5 class prime_t
  6 {
  7 private:
  8   long max_number;
  9   long blocks;
 10   char *a_primes;
 11
 12 public:
 13   prime_t(long max_number = 100);
 14   virtual ~prime_t();
 15
 16   bool is_prime(long number) { return get(number); }
 17
 18 private:
 19   void init();
 20   void release();
 21
 22   void set(long number, bool flag);
 23   bool get(long number);
 24 };
 25
 26 prime_t::prime_t(long max_number)
 27   : max_number(max_number),
 28     a_primes(0),
 29     blocks(1)
 30 {
 31   init();
 32 }
 33 prime_t::~prime_t()
 34 {
 35   release();
 36 }
 37 void prime_t::init()
 38 {
 39   if (max_number <= 1) {
 40     max_number = 100;
 41   }
 42   blocks = (max_number/8) + 1;
 43   a_primes = new char[blocks];
 44   memset(a_primes, 0xff, blocks);
 45
 46   set(0, false); set(1, false);
 47
 48   for (long l=2; l<=max_number; ++l) {
 49     if (!get(l)) continue;
 50     for (long l2=l*2; l2<=max_number; l2+=l) {
 51       set(l2, false);
 52     }
 53   }
 54 }
 55 void prime_t::release()
 56 {
 57   if (a_primes) {
 58     delete[] a_primes;
 59   }
 60   a_primes = 0;
 61 }
 62 void prime_t::set(long number, bool flag)
 63 {
 64   long block = number/8;
 65   int  pos   = number%8;
 66   char mask  = ~(0x01 << pos);
 67   a_primes[block] = (a_primes[block] & mask) | ((0x01 & (char)flag) << pos);
 68 }
 69 bool prime_t::get(long number)
 70 {
 71   long block = number/8;
 72   int  pos   = number%8;
 73   char mask  = (0x01 << pos);
 74   return (a_primes[block] & mask );
 75 }
 76
 77 int main(int argc, char *argv[])
 78 {
 79   long max_number = (argc > 1 ? atol(argv[1]) : 100);
 80   prime_t prime(max_number);
 81
 82   int cnt = 1;
 83   for (long l=0; l<=max_number; ++l) {
 84     if (!prime.is_prime(l)) continue;
 85     printf("%8ld%s", l, (cnt%10 == 0 ? "\n" : ""));
 86     ++cnt;
 87   }
 88   printf("\n");
 45
 46   set(0, false); set(1, false);
 47
 48   for (long l=2; l<=max_number; ++l) {
 49     if (!get(l)) continue;
 50     for (long l2=l*2; l2<=max_number; l2+=l) {
 51       set(l2, false);
 52     }
 53   }
 54 }
 55 void prime_t::release()
 56 {
 57   if (a_primes) {
 58     delete[] a_primes;
 59   }
 60   a_primes = 0;
 61 }
 62 void prime_t::set(long number, bool flag)
 63 {
 64   long block = number/8;
 65   int  pos   = number%8;
 66   char mask  = ~(0x01 << pos);
 67   a_primes[block] = (a_primes[block] & mask) | ((0x01 & (char)flag) << pos);
 68 }
 69 bool prime_t::get(long number)
 70 {
 71   long block = number/8;
 72   int  pos   = number%8;
 73   char mask  = (0x01 << pos);
 74   return (a_primes[block] & mask );
 75 }
 76
 77 int main(int argc, char *argv[])
 78 {
 79   long max_number = (argc > 1 ? atol(argv[1]) : 100);
 80   prime_t prime(max_number);
 81
 82   int cnt = 1;
 83   for (long l=0; l<=max_number; ++l) {
 84     if (!prime.is_prime(l)) continue;
 85     printf("%8ld%s", l, (cnt%10 == 0 ? "\n" : ""));
 86     ++cnt;
 87   }
 88   printf("\n");
 89
 90   return 0;
 91 }
 92