From bf717b19d8279f0a9b908d1f465a821d43f3eb55 Mon Sep 17 00:00:00 2001
From: Stephen Lynn <bizlsg@localhost.localdomain>
Date: Sat, 11 Jun 2022 20:41:39 +0800
Subject: improved raku ch-2

---
 challenge-168/steve-g-lynn/raku/ch-2.p6 | 115 ++++++--------------------------
 1 file changed, 20 insertions(+), 95 deletions(-)

diff --git a/challenge-168/steve-g-lynn/raku/ch-2.p6 b/challenge-168/steve-g-lynn/raku/ch-2.p6
index bfe46ec923..f3a1259691 100755
--- a/challenge-168/steve-g-lynn/raku/ch-2.p6
+++ b/challenge-168/steve-g-lynn/raku/ch-2.p6
@@ -1,126 +1,51 @@
 #!/usr/bin/raku
 
 #time (bash command): 
-#real	0m0.490s
-#user	0m0.729s
-#sys	0m0.056s
-
-
-# acknowledgement:
-
-# I improved the previous grossly inefficient version 
-# (> 1 min script run time) after looking 
-# at the raku and python submissions from Roger Bell-West
+#real	0m0.511s
+#user	0m0.622s
+#sys	0m0.046s
 
 
 say homeprime(10);
 #773
 say homeprime(16);
 #31636373
+say homeprime(20);
+#3318308475676071413
 
 #-- sub for home prime
 
-sub homeprime(Int $n) returns Int { 
+sub homeprime(Int $n) returns Int {
 	$n.Int.is-prime && return $n;
-	my $ncopy=$n;
-	while (1) {
-		my $last=$ncopy;
-		$ncopy=factor($ncopy);
-		($ncopy==$last) && last;
-	}
-	return $ncopy;
+	return homeprime(factor($n));
 }
 
 #--sub for factorizing
 
-multi sub factor (1) returns Int {1}
-
-multi sub factor (Int $n where $n > 1) returns Int {
+sub factor (Int $n where $n > 1) returns Int {
 #-- returns the concatenated prime factors as an int
 	$n.Int.is-prime && (return $n.Int );
-	my $sqrt_n = sqrt($n).Int+1;
-	my @primes=find_primes($sqrt_n);
+	my Int $sqrt_n = sqrt($n).Int;
+
 	my @factors=();
 
-	my $retstring="";
-	my $ncopy=$n;	
+	my Str $retstring="";
+	my Int $ncopy=$n.Int;	
 	
-	for @primes -> $prime {
-		while ( ($ncopy % $prime)==0) {
-			$ncopy /= $prime;
-			push @factors, $prime;
+	for (2 .. $sqrt_n) -> $prime {
+	#-- no need to generate primes first.. the routine will 
+	#-- automatically only choose prime factors
+		while ($ncopy %% $prime) {
+			$ncopy div= $prime; 	#-- integer division
+			@factors.append($prime);
 		}
+		$ncopy.is-prime && last;
 	}
-	($ncopy > 1) && push @factors, $ncopy;
+	($ncopy > 1) && @factors.append($ncopy);
 	#-- any factor bigger than sqrt(n) is a prime factor
 	$retstring = @factors.list.join;
 
 	return $retstring.Int;
 }
 
-multi sub find_primes(Int $n where $n <= 100) {
-	my @primes=
-	(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97); 
-	my @retval=();
-	for @primes -> $prime {
-		($prime < $n) && (push @retval, $prime);
-	}
-	return (@retval.sort);
-}
-
-multi sub find_primes (Int $n where $n > 100) {
-	my @primes=[7,11,13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]; #-- candidate primes
-	my %primes{Int}=(); #-- we will return keys of this
-	my $sqrt_n = sqrt($n); #-- ceiling for iterating thru' sieve
-	
-	#-- initialize primes hash
-	#-- store candidates of the form 6k-1 to 6k+1
-	#-- eliminate multiples of known primes
-	loop (my $i=102; $i <= $n+1; $i += 6) {
-		my @temp=($i-1, $i+1);
-		TEMP: for @temp -> $temp {
-			($temp % 3) || next;
-			($temp % 5) || next;
-			for @primes -> $prime {
-				($prime > $sqrt_n) && last;
-				($temp % $prime) || next TEMP;
-			}
-			($temp <= $n) && (%primes{$temp}=True);
-		}
-	}
-		
-	#-- for prime candidates k greater than @primes[*-1]
-	#-- use odd numbers not divisible by 3 (last value + 4 and +6 if
-	#   we start counting from 97)
-	#-- loop through factors kk+jk < n and delete
-	#-- any %hash entries with key matching these factors.
-
-	my $last_prime = @primes[*-1];
-	if ($last_prime < $sqrt_n) { 
-		@primes=[$last_prime+4, $last_prime+2];
-		while (1) {
-			my $prime = shift @primes;
-			(@primes.elems==0) && 
-				(@primes.append($prime+4, $prime+2));
-			#-- avoid multiples of 3
-			
-			last if $prime > $sqrt_n;
-		
-			#-- only loop if the candidate is in the primes hash
-			if  ( %primes{$prime} ) {
-				loop (my $i=$prime*$prime; 
-					$i <= $n;
-					$i += $prime) {
-						%primes{$i}:delete;
-				}
-			}
-		}
-	}
-	my @retval=(2,3,5,7,11,13,17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97);
-	return (@retval.append(%primes.keys.sort));
-
-	return 1;
-}
-
-
 
-- 
cgit