/usr/share/nickle/prime_sieve.5c is in nickle 2.77-1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 | /*
* Copyright © 2010 Keith Packard and Bart Massey.
* All Rights Reserved. See the file COPYING in this directory
* for licensing information.
*/
public namespace PrimeSieve {
int num_to_pos(int n) = (n - 3) // 2;
int pos_to_num(int p) = (p * 2) + 3;
/* Generate a list of primes from a boolean array of composite
* test results
*/
int[] sieve_to_array(&bool[] composite, int n_prime) {
int[n_prime] primes;
int p = 0;
for (int i = 0; i < dim(composite); i++)
if (!composite[i])
primes[p++] = pos_to_num(i);
return primes;
}
/* Use the sieve of Eratosthenes to compute the set of
* primes <= max
*/
public int[] primes (int max)
{
int n = num_to_pos(max) + 1;
bool[n] composite = { false ... };
int n_prime = 0;
for (int p = 0; p < n; p++) {
if (!composite[p]) {
int prime = pos_to_num(p);
int step = prime;
int init = p + prime;
for (int v = init; v < n; v += step)
composite[v] = true;
n_prime++;
}
}
return sieve_to_array(&composite, n_prime);
}
public typedef struct {
int start, end;
} range_t;
/* Binary search in a list of numbers for the value <= 'v' */
public int primes_search(&int[] primes, int v) {
int min = 0, max = dim(primes);
while (min < max) {
int mid = (max + min) >> 1;
int p = primes[mid];
if (p == v)
return mid;
if (p > v)
max = mid;
else {
if (min == mid)
return mid;
min = mid;
}
}
return min;
}
/* Return the indices within a list of primes such that
* primes[start] <= min && max < primes[end]
*/
public range_t primes_range(&int[] primes, int min, int max) {
int start = primes_search(&primes, min);
if (primes[start] < min) start++;
int end = primes_search(&primes, max) + 1;
return (range_t) { start = start, end = end };
}
/*
* Multiply all primes between min and max within the
* supplied list.
*/
public int primorial(&int[] primes, int min, int max) {
range_t r = primes_range(&primes, min, max);
int v = 1;
for (int i = r.start; i < r.end; i++)
v *= primes[i];
return v;
}
}
|