diff options
| -rwxr-xr-x | challenge-168/steve-g-lynn/julia/ch-2.jl | 15 | ||||
| -rwxr-xr-x | challenge-168/steve-g-lynn/raku/ch-2.p6 | 69 |
2 files changed, 61 insertions, 23 deletions
diff --git a/challenge-168/steve-g-lynn/julia/ch-2.jl b/challenge-168/steve-g-lynn/julia/ch-2.jl new file mode 100755 index 0000000000..19d4c7d498 --- /dev/null +++ b/challenge-168/steve-g-lynn/julia/ch-2.jl @@ -0,0 +1,15 @@ +#! /usr/bin/julia + +using Primes + +function homeprime(n::Int64) + ncopy=n + while (!isprime(ncopy)) + ncopy=parse(Int64,join(factor(Vector,ncopy))) + end + return ncopy +end + +println(homeprime(16)) +#31636373 + diff --git a/challenge-168/steve-g-lynn/raku/ch-2.p6 b/challenge-168/steve-g-lynn/raku/ch-2.p6 index 71fa044657..b4183fd6d3 100755 --- a/challenge-168/steve-g-lynn/raku/ch-2.p6 +++ b/challenge-168/steve-g-lynn/raku/ch-2.p6 @@ -2,8 +2,7 @@ say homeprime(16); # 31636373 -#-- works but very slow: time real 0m59.301s user 0m58.334s sys 0m0.773s -#-- on MacBook Air running Linux FC36 +#-- works but slow #-- sub for home prime @@ -22,7 +21,8 @@ multi sub factor (1) {1} multi sub factor (Int $n where $n > 1){ #-- returns string concatenation of prime factors - my @primes=prime_sieve($n); +# my @primes=prime_sieve($n); + my @primes=find_primes($n); my $retstring=""; my $ncopy=$n; @@ -37,25 +37,48 @@ multi sub factor (Int $n where $n > 1){ return $retstring; } -#--sub for sieve of Eratosthenes -#-- (algorihm from wikipedia) -sub prime_sieve(Int $n where $n > 1){ - my @a = 2..$n; - my (%retval=(),@retval=()); - for (@a) -> $i { - %retval{$i}=1; - } - my @i= 2..round(sqrt($n)); - for @i -> $i { - loop ( my $j=($i*$i); $j <= $n; $j += $i){ - %retval{$j}=0; - } - } - my @k = %retval.keys; - for @k -> $k { - if (%retval{$k}==1) { - push @retval, $k; - } +multi sub find_primes(Int $n where $n <= 13) { + my @primes=(2,3,5,7,11,13); + my @retval=(); + for @primes -> $prime { + ($prime < $n) && (push @retval, $prime); } - return (@retval.sort:{$^a <=> $^b}); + return (@retval.sort); } + +multi sub find_primes(Int $n where $n > 13) { +#-- naive approach by trial factorization + my @primes=(3,7,11,13); + + my $i=13; + + while ($i < $n) { + #-- count only odd numbers not ending in 5. Take 4 at a time. + my @testarray=(); + + (($i+4) < $n) && (push @testarray, ($i+4)); + (($i+6) < $n) && (push @testarray, ($i+6)); + (($i+8) < $n) && (push @testarray, ($i+8)); + (($i+10) < $n) && (push @testarray, ($i+10)); + + while (@testarray.elems > 0) { + my $testitem=shift(@testarray); + unless ((($testitem % 6)==1) || (($testitem % 6)==5)) { + #-- use the property that prime numbers above 5 are 6k+1 or 6k-1 + next; + } + for @primes -> $prime { + ($prime > sqrt($testitem)) && last; + (($testitem % $prime)==0) && last; + } + push @primes, $testitem; + } + $i += 10; + } + + splice(@primes,0,1, <2 3 5>); #-- left out 2 and 5 earlier to avoid + # unnecessary redundant factorizing + return (@primes.sort); +} + + |