Count in factors: Difference between revisions
m (→{{header|Perl 6}}: remove some extraneous punctuation) |
(→{{header|Perl 6}}: A more symbolic implementation; factors are returned as an array, and formatted by the caller to factor().) |
||
Line 5: | Line 5: | ||
=={{header|Perl 6}}== |
=={{header|Perl 6}}== |
||
The two <tt>multi prime</tt> lines are adapted from Perl 6's entry at [[Primality by Trial Division]]. |
The first two <tt>multi prime</tt> lines are adapted from Perl 6's entry at [[Primality by Trial Division]]. |
||
<lang perl6>multi prime (Int $n --> Bool) { |
<lang perl6>multi prime (Int $n --> Bool) { |
||
$n %% none 2, 3, *+2 ...^ * > sqrt $n; |
$n %% none 2, 3, *+2 ...^ * > sqrt $n; |
||
Line 16: | Line 16: | ||
sub next_prime(Int $start --> Int) { |
sub next_prime(Int $start --> Int) { |
||
my $check = $start + 1; |
my $check = $start + 1; |
||
if $check %% 2 and $check > 2 { ++$check } |
if $check %% 2 and $check > 2 { ++$check } |
||
until prime($check) { $check += 2 } |
until prime($check) { $check += 2 } |
||
Line 25: | Line 25: | ||
my @primes := 2, -> $a { next_prime($a) } ... *; |
my @primes := 2, -> $a { next_prime($a) } ... *; |
||
multi factor(Int $inFactor where ( $inFactor == 1 ) ) |
|||
say "1: 1"; |
|||
{ |
|||
(1); |
|||
} |
|||
multi factor(Int $toFactor) |
|||
⚫ | |||
{ |
|||
⚫ | |||
my $currentRemainder = $toFactor; |
|||
#say "L1 ... $_"; |
|||
⚫ | |||
my $currentProduct = 1; |
|||
# It's not prime? Find its prime factors. |
|||
⚫ | |||
⚫ | |||
my $prime_index = 0; |
|||
⚫ | |||
my @factors; |
|||
⚫ | |||
my $factor = @primes[$prime_index]; |
|||
⚫ | |||
if $currentProduct == 1 { print $factor } else { print " x $factor" } |
|||
⚫ | |||
⚫ | |||
# |
# Find a factor of our current remainder. |
||
⚫ | |||
$toFactor /= $factor; |
|||
$currentProduct *= $factor; |
|||
⚫ | |||
@factors.push(@primes[$primeIndex]); |
|||
# Some bookkeeping. |
|||
$currentRemainder /= @primes[$primeIndex]; |
|||
} |
} |
||
say ""; |
|||
@factors; |
|||
} |
|||
⚫ | |||
{ |
|||
⚫ | |||
say factor($_).join(" x "); |
|||
}</lang> |
}</lang> |
||
Revision as of 01:46, 24 December 2010
Write a program which counts up from 1, displaying each number as the multiplication of its prime factors. For the purpose of this task, may be shown as itself.
For examle, is prime, so it would be shown as itself. is not prime; it would be shown as . Likewise, 2144 is not prime; it would be shown as .
Perl 6
The first two multi prime lines are adapted from Perl 6's entry at Primality by Trial Division. <lang perl6>multi prime (Int $n --> Bool) {
$n %% none 2, 3, *+2 ...^ * > sqrt $n;
}
multi prime (Int $n where ( $n <= 1)) {
False;
}
sub next_prime(Int $start --> Int) {
my $check = $start + 1; if $check %% 2 and $check > 2 { ++$check }
until prime($check) { $check += 2 }
return $check;
}
my @primes := 2, -> $a { next_prime($a) } ... *;
multi factor(Int $inFactor where ( $inFactor == 1 ) ) {
(1);
}
multi factor(Int $toFactor) {
my $currentRemainder = $toFactor;
my @factors;
# Iterate through our primes until we find a prime number that's a factor of $currentRemainder; until 1 == $currentRemainder { my $primeIndex = 0;
# Find a factor of our current remainder. until $currentRemainder %% @primes[$primeIndex] { ++$primeIndex }
# We found our next factor. @factors.push(@primes[$primeIndex]);
# Some bookkeeping. $currentRemainder /= @primes[$primeIndex]; }
@factors;
}
for(1..*) {
print "$_: "; say factor($_).join(" x ");
}</lang>
The first twenty numbers:
1: 1 2: 2 3: 3 4: 2 x 2 5: 5 6: 2 x 3 7: 7 8: 2 x 2 x 2 9: 3 x 3 10: 2 x 5 11: 11 12: 2 x 2 x 3 13: 13 14: 2 x 7 15: 3 x 5 16: 2 x 2 x 2 x 2 17: 17 18: 2 x 3 x 3 19: 19 20: 2 x 2 x 5
PicoLisp
Use the 'factor' function from Prime decomposition#PicoLisp. <lang PicoLisp>(for N 20
(prinl N ": " (or (glue " * " (factor N)) 1)) )</lang>
Output:
1: 1 2: 2 3: 3 4: 2 * 2 5: 5 6: 2 * 3 7: 7 8: 2 * 2 * 2 9: 3 * 3 10: 2 * 5 11: 11 12: 2 * 2 * 3 13: 13 14: 2 * 7 15: 3 * 5 16: 2 * 2 * 2 * 2 17: 17 18: 2 * 3 * 3 19: 19 20: 2 * 2 * 5