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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
|
#!/usr/env perl
# PerlWeeklyChallenge 41-1
# Attractive number: - a number that has a prime number of prime factors:
# Task:- identify first 20 attractive numbers
# Identifying number of primes factors may be done by repeated testing of
# a series of increasing potential factors. This task can be intensive
# unless rationalised somehow. The actual number of steps can be reduced by
#
# 1) setting a limit for search: square (root of number + 1)
# 2) search only odd numbers after 2, or search only known prime numbers
# 3) reducing limit after every factor identified.
#
# The search can be made even faster, if one caches: -
# 1) the discovered factors
# 2) the discovered primes
# this increase in performance happens at the expense of memory and depends on
# preloading
#
# The following solution offered, demonstrates 3 methods of factorisation.
# Each method is encapsulated in a hash which offers also functions
# factorise(), isPrime(), numberOfFactors() and isAttractive()
# The first method offers no caching, second method caches factors and
# third caches the primes and the factors. The first requires no preloading
# the second and third preload. All three methods are tested using benchmark();
# NOTE use strict and use warnings are not used becaiuse of the naughty way
# the solution encapsulates each method of factorisation inside a hash
initialise();
getAttractive(20,"method2");
benchmark();
sub getAttractive{ # gets attractive numbers
my $n=shift; # how many to get
$method=shift //"method1"; # which method to use or use method1
print "Using $method the first $n attractive numbers are:-\n";
my $candidate=0; # number to test for attractiveness
while ($n--) {
# increment $candidate until attractive found
while (!${$method}{isAttractive}->(++$Candidate)){};
# display attarctive numbers and factors
print "$Candidate is attractive; Factors are ",
(join ",",(defined ${$method}{factors}) ? # if a cache of factors exists
@{${$method}{factors} ->[$Candidate]} : # retrieve from cache or
@{${$method}{factorise}->($Candidate)} ),# just factorise again
"\n";
}
}
sub initialise{
# Method1 caches nothing. The factorise function return the list of factors, or
# just the number itself if it is prime
%method1=( # "our" used to make it available
# outsibe the initialise subroutine
factorise=>sub {
my $wn=$number=shift; # the number to test is loaded
my @factorsList=(); # the aray of factors found
my $test=2; # start search with 2 as a factor
my $limit=sqrt($wn+1); # continue to a reasonable limit
while ($test < $limit){ # until limit passed
if ($wn % $test){ # if not a factor (i.e. $wn % $test is not zero
$test++; # test next number
$test++ unless $test==3; # ensure that after 2 only odd numbers are tested
}
else{ # factor found
push @factorsList,$test;# store factor in our list
$wn=$wn/$test; # and factorise the rest...
$limit=sqrt($wn+1) # ...resetting limit accordingly
}
}
return [@factorsList,$wn]; # return all factors found (including the last prime)
},
isPrime=>sub{ # all methods retun the number if no factors are found
my $t=shift;
return 0 if $t<2; # 0 and 1 are not prime numbers
return $method1{ numberOfFactors}->($t)==1?1:0;
},
numberOfFactors=>sub{ # list of factors obtained by factorise
my $t=shift;
return scalar @{$method1{factorise}->($t)};
},
isAttractive=>sub { # tests that numberOfFactors() isPrime()
my $t=shift;
return $method1{isPrime}->( $method1{numberOfFactors}->( $t ) );
},
);
# Method 2 caches the factors. Because the factors of previously tested numbers are
# retained only the smallest factor is required, and it merely retrieves the rest
# from the cache
%method2=(
factorise=>sub {
my $number=shift; # the number to test is loaded
# if number already has ached factors, retieve from cache
return $method2{factors}->[$number] if (defined $method2{factors}->[$number]) ;
my $test=2; $limit=sqrt($number+1); # as before start with 2 and set limits
while (($test < $limit)&&($number % $test)){
$test++;
$test++ unless $test==3;
}
if ($test<$limit){ # found the smallest prime factor.
# Because of caching, all the other factors have
# already been found, no need to search.
$method2{factors}->[$number]= [$test,@{$method2{factors}->[$number/$test]}]
}
else{ #otherwise this is a prime number, store in cache
$method2{factors}->[$number]= [$number];
}
return $method2{factors}->[$number];
},
isPrime=>sub{
my $t=shift;
return 0 if $t<2;
return $method2{numberOfFactors}->($t)==1?1:0;
},
numberOfFactors=>sub{ # retrieve from cache
my $t=shift;
return scalar @{$method2{factors}->[$t]};
},
isAttractive=>sub{ # tests that numberOfFactors() isPrime()
my $t=shift;
return $method2{isPrime}->( $method2{numberOfFactors}->( $t ) );
},
factors=>[], # cache of factors
);
# Method 3 caches factors and primes.
# the primes cache is a hash, with each prime stored as key, with next key as its value
# e.g 2=>3,3=>5,5=>7,7=>11,11=>-1,largest=>11. this allows quick retrieval of the next
# found poetntial prime factor.
%method3=(
factorise=>sub{
my $number=shift;
return $method3{factors}->[$number] if (defined $method3{factors}->[$number]) ;
my $test=2; my $limit=sqrt($number+1);
while (($test < $limit)&&($number % $test)){
$test=$method3{primes}->{$test}; # test larger and larger primes
}
if (($number % $test)||($number/$test ==1)){ # no old prime factor found
# number must be a new prime larger than one previously encountered
# this is stored in a hash, replacing previous largest prime
# this method of setting multiple values in a hash is not possible with "strict"
@method3{primes}->{$number,$method3{primes}->{"largest"},{"largest"} }=(-1,$number,$number);
$method3{factors}->[$number]= [$number];
}
else{
$method3{factors}->[$number]=[$test,@{$method3{factors}->[$number/$test]}];
}
return $method3{factors}->[$number];
},
isPrime=>sub{ # check primes from the hash cache
my $t=shift;
return 0 if $t<2;
return defined $method3{primes}->{$t}?1:0;
},
numberOfFactors=>sub{
my $t=shift;
return scalar @{$method3{factors}->[$t]}; # check factors from the cache array
},
isAttractive=>sub{ # tests that numberOfFactors() isPrime()
my $t=shift;
return $method3{isPrime}->( $method3{numberOfFactors}->( $t ) );
},
primes =>{2=>3,3=>5,5=>7,7=>11,11=>-1,largest=>11},
factors=>[],
);
for my $method ("method2","method3"){
for (1..100){
${$method}{factorise}->($_)
}
}
}
# This routine benchmarks the three methods twice, demonstrating the
# effectiveness of caching at first and subsequent passes.
sub benchmark{
use Time::HiRes qw ( time);
my $start;
for (1,2){
print "Benchmark pass $_\n";
for my $end (1000,10000,100000){
for my $method (1..3){
$start=time();
for (1..$end){
${"method$method"}{factorise}->($_)
}
${"duration$method"}= int (1000*(time()-$start));
}
print "With $end factorisations: Method1 $duration1 ms Method2 $duration2 ms Method3 $duration3 ms \n";
}
}
}
# output
#
# Using method2 the first 20 attractive numbers are:-
# 4 is attractive; Factors are 2,2
# 6 is attractive; Factors are 2,3
# 8 is attractive; Factors are 2,2,2
# 9 is attractive; Factors are 3,3
# 10 is attractive; Factors are 2,5
# 12 is attractive; Factors are 2,2,3
# 14 is attractive; Factors are 2,7
# 15 is attractive; Factors are 3,5
# 18 is attractive; Factors are 2,3,3
# 20 is attractive; Factors are 2,2,5
# 21 is attractive; Factors are 3,7
# 22 is attractive; Factors are 2,11
# 25 is attractive; Factors are 5,5
# 26 is attractive; Factors are 2,13
# 27 is attractive; Factors are 3,3,3
# 28 is attractive; Factors are 2,2,7
# 30 is attractive; Factors are 2,3,5
# 32 is attractive; Factors are 2,2,2,2,2
# 33 is attractive; Factors are 3,11
# 34 is attractive; Factors are 2,17
# Benchmark pass 1
# With 1000 factorisations: Method1 4 ms Method2 2 ms Method3 3 ms
# With 10000 factorisations: Method1 58 ms Method2 35 ms Method3 26 ms
# With 100000 factorisations: Method1 934 ms Method2 397 ms Method3 233 ms
# Benchmark pass 2
# With 1000 factorisations: Method1 3 ms Method2 0 ms Method3 0 ms
# With 10000 factorisations: Method1 49 ms Method2 5 ms Method3 5 ms
# With 100000 factorisations: Method1 895 ms Method2 54 ms Method3 51 ms
|
