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
