| 1 |
#include <stdio.h> |
| 2 |
|
| 3 |
void abort (void); |
| 4 |
void exit (int); |
| 5 |
|
| 6 |
/* Convert a decimal string to a long long unsigned. No error check is |
| 7 |
performed. */ |
| 8 |
|
| 9 |
long long unsigned |
| 10 |
str2llu (str) |
| 11 |
char *str; |
| 12 |
{ |
| 13 |
long long unsigned acc; |
| 14 |
int d; |
| 15 |
acc = *str++ - '0'; |
| 16 |
for (;;) |
| 17 |
{ |
| 18 |
d = *str++; |
| 19 |
if (d == '\0') |
| 20 |
break; |
| 21 |
d -= '0'; |
| 22 |
acc = acc * 10 + d; |
| 23 |
} |
| 24 |
|
| 25 |
return acc; |
| 26 |
} |
| 27 |
|
| 28 |
/* isqrt(t) - computes the square root of t. (tege 86-10-27) */ |
| 29 |
|
| 30 |
long unsigned |
| 31 |
sqrtllu (long long unsigned t) |
| 32 |
{ |
| 33 |
long long unsigned s; |
| 34 |
long long unsigned b; |
| 35 |
|
| 36 |
for (b = 0, s = t; b++, (s >>= 1) != 0; ) |
| 37 |
; |
| 38 |
|
| 39 |
s = 1LL << (b >> 1); |
| 40 |
|
| 41 |
if (b & 1) |
| 42 |
s += s >> 1; |
| 43 |
|
| 44 |
do |
| 45 |
{ |
| 46 |
b = t / s; |
| 47 |
s = (s + b) >> 1; |
| 48 |
} |
| 49 |
while (b < s); |
| 50 |
|
| 51 |
return s; |
| 52 |
} |
| 53 |
|
| 54 |
|
| 55 |
int plist (p0, p1, tab) |
| 56 |
long long unsigned p0, p1; |
| 57 |
long long unsigned *tab; |
| 58 |
{ |
| 59 |
long long unsigned p; |
| 60 |
long unsigned d; |
| 61 |
long unsigned s; |
| 62 |
long long unsigned *xp = tab; |
| 63 |
|
| 64 |
for (p = p0; p <= p1; p += 2) |
| 65 |
{ |
| 66 |
s = sqrtllu (p); |
| 67 |
|
| 68 |
for (d = 3; d <= s; d += 2) |
| 69 |
{ |
| 70 |
long long unsigned q = p % d; |
| 71 |
if (q == 0) |
| 72 |
goto not_prime; |
| 73 |
} |
| 74 |
|
| 75 |
*xp++ = p; |
| 76 |
not_prime:; |
| 77 |
} |
| 78 |
*xp = 0; |
| 79 |
return xp - tab; |
| 80 |
} |
| 81 |
|
| 82 |
int |
| 83 |
main (argc, argv) |
| 84 |
int argc; |
| 85 |
char *argv[]; |
| 86 |
{ |
| 87 |
long long tab[10]; |
| 88 |
int nprimes; |
| 89 |
nprimes = plist (str2llu ("1234111111"), str2llu ("1234111127"), tab); |
| 90 |
|
| 91 |
if(tab[0]!=1234111117LL||tab[1]!=1234111121LL||tab[2]!=1234111127LL||tab[3]!=0) |
| 92 |
abort(); |
| 93 |
|
| 94 |
exit(0); |
| 95 |
} |