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