00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00053
00054 #include <stdio.h>
00055 #include <stdarg.h>
00056 #include <sys/param.h>
00057 #include <imath.h>
00058
00059
00060
00061
00062
00063
00064
00065
00066 #if DATA_SIZE > 8192 + 512
00067 # undef DATA_SIZE
00068 # define DATA_SIZE 8192 + 512
00069 #endif
00070
00071
00072 #if DATA_SIZE < 512
00073 # define MAX_PRIMES (DATA_SIZE - 128)
00074 #else
00075 # define MAX_PRIMES (DATA_SIZE - 512)
00076 #endif
00077
00078 #define LAST_PRIME (MAX_PRIMES * 8L)
00079
00080
00081 unsigned char prime_list[MAX_PRIMES];
00082
00083
00084 static inline int
00085 is_prime (unsigned long n)
00086 {
00087 unsigned short bit = (unsigned short) (n) & 0x07;
00088
00089 return prime_list[n >> 3] & (1 << bit);
00090 }
00091
00092
00093 static inline void
00094 set_prime (unsigned long n)
00095 {
00096 unsigned short bit = (unsigned short) (n) & 0x07;
00097
00098 prime_list[n >> 3] |= (1 << bit);
00099 }
00100
00101
00102
00103 int
00104 check_for_prime (unsigned long n)
00105 {
00106 unsigned long i;
00107 unsigned char *p;
00108 unsigned long last_value;
00109 unsigned char small_n;
00110
00111 small_n = (n & 0xffff0000) == 0;
00112 i = 0;
00113
00114
00115 last_value = lsqrt (n);
00116
00117
00118
00119 p = prime_list;
00120 do
00121 {
00122 unsigned char val;
00123
00124 val = *p++;
00125 if (val)
00126 {
00127 unsigned short j;
00128 unsigned long q;
00129
00130 q = i;
00131 for (j = 1; val && j <= 0x80; j <<= 1, q++)
00132 {
00133 if (val & j)
00134 {
00135 val &= ~j;
00136
00137
00138 if (small_n)
00139 {
00140 unsigned short r;
00141
00142
00143 r = (unsigned short) (n) % (unsigned short) (q);
00144 if (r == 0)
00145 return 0;
00146 }
00147 else
00148 {
00149 unsigned long r;
00150
00151 r = n % q;
00152
00153
00154 if (r == 0)
00155 return 0;
00156 }
00157 }
00158 }
00159 }
00160 i += 8;
00161 }
00162 while (i < last_value);
00163 return 1;
00164 }
00165
00166
00167
00168 void
00169 print_primes ()
00170 {
00171 long i;
00172
00173 for (i = 0; i < LAST_PRIME; i++)
00174 if (is_prime (i))
00175 printf ("%ld\n", i);
00176 }
00177
00178
00179
00180 int verbose = 0;
00181
00182 int
00183 main ()
00184 {
00185 long i;
00186 short cnt = 0;
00187
00188 printf ("Computing prime numbers below %ld\n",
00189 (long) LAST_PRIME);
00190 memset (prime_list, 0, sizeof (prime_list));
00191 for (i = 2; i < LAST_PRIME; i++)
00192 {
00193 if (check_for_prime (i))
00194 {
00195 set_prime (i);
00196 cnt ++;
00197 if (verbose)
00198 printf ("%ld\n", i);
00199 }
00200 }
00201 printf ("Found %ld prime numbers below %ld\n",
00202 (long) cnt, (long) LAST_PRIME);
00203
00204 return 0;
00205 }