blob: be03a6e3b0a481b44dd31a0cb98c0b56e4f00c70 (
plain)
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
91
92
93
94
95
96
97
|
#!/usr/bin/perl -w
# -*- perl -*-
eval 'exec /usr/bin/perl -S $0 ${1+"$@"}'
if 0;
use strict;
(my $program_name = $0) =~ s|.*/||;
sub END
{
use POSIX qw (_exit);
# This is required if the code might send any output to stdout
# E.g., even --version or --help. So it's best to do it unconditionally.
close STDOUT
or (warn "$program_name: closing standard output: $!\n"), _exit (1);
}
sub is_prime ($)
{
my ($n) = @_;
use integer;
$n == 2
and return 1;
my $d = 2;
my $w = 1;
while (1)
{
my $q = $n / $d;
$n == $q * $d
and return 0;
$d += $w;
$q < $d
and last;
$w = 2;
}
return 1;
}
{
@ARGV == 1
or die "$program_name: missing argument\n";
my $wheel_size = $ARGV[0];
my @primes = (2);
my $product = $primes[0];
my $n_primes = 1;
for (my $i = 3; ; $i += 2)
{
if (is_prime $i)
{
push @primes, $i;
$product *= $i;
++$n_primes == $wheel_size
and last;
}
}
my $ws_m1 = $wheel_size - 1;
print <<EOF;
/* The first $ws_m1 elements correspond to the incremental offsets of the
first $wheel_size primes (@primes). The $wheel_size(th) element is the
difference between that last prime and the next largest integer
that is not a multiple of those primes. The remaining numbers
define the wheel. For more information, see
http://www.utm.edu/research/primes/glossary/WheelFactorization.html. */
EOF
my @increments;
my $prev = 2;
for (my $i = 3; ; $i += 2)
{
my $rel_prime = 1;
foreach my $divisor (@primes)
{
$i != $divisor && $i % $divisor == 0
and $rel_prime = 0;
}
if ($rel_prime)
{
#warn $i, ' ', $i - $prev, "\n";
push @increments, $i - $prev;
$prev = $i;
$product + 1 < $i
and last;
}
}
print join (",\n", @increments), "\n";
exit 0;
}
|
