1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
namespace;
include rt;
// primes below 60000: an o3 sieve over a fixed array, the primes
// gathered into a growable one, then a few questions asked of them.
// with ZYTRACE=1 the o3 lines show each region being lifted and compiled.
// marks the composites; f[i] ends up 1 for every prime i
o3 int sieve(fixed int[?] f) {
int n = len(f), c = 0;
for (int i = 2; i < n; i++) f[i] = 1;
for (int i = 2; i * i < n; i++)
if (f[i]) for (int j = i * i; j < n; j += i) f[j] = 0;
for (int i = 2; i < n; i++) c += f[i];
return c;
}
// the largest gap between neighbours, and where it starts
o3 int gap(fixed int[?] f, int* at) {
int n = len(f), last = 2, best = 0, where = 0;
for (int i = 3; i < n; i++)
if (f[i]) { if (i - last > best) { best = i - last; where = last; } last = i; }
*at = where;
return best;
}
void main() {
fixed int[?] f = rt.new(fixed int[?], 60000);
int[?] ps = rt.new(int[?]);
int c = sieve(f), at = 0, twins = 0;
for (int i = 2; i < len(f); i++) if (f[i]) push(ps, i);
o3 { for (int k = 1; k < len(ps); k++) if (ps[k] - ps[k - 1] == 2) twins++; }
rt.put_s("primes below 60000: "); rt.put_n(c); rt.put_c(10);
rt.put_s("the last five:"); for (int k = len(ps) - 5; k < len(ps); k++) { rt.put_c(' '); rt.put_n(ps[k]); } rt.put_c(10);
rt.put_s("twin pairs: "); rt.put_n(twins); rt.put_c(10);
int g = gap(f, &at);
rt.put_s("widest gap: "); rt.put_n(g); rt.put_s(", after "); rt.put_n(at); rt.put_c(10);
rt.free(f); rt.free(ps);
return;
}
|
