Almost prime: Difference between revisions
Content added Content deleted
m (→{{header|Perl 6}}: adding introductory comment) |
m (→{{header|Perl 6}}: minor style change) |
||
Line 9: | Line 9: | ||
Recursive implementation. Quite slow. |
Recursive implementation. Quite slow. |
||
<lang perl6>sub is-k-almost-prime($n, $k) { |
<lang perl6>sub is-k-almost-prime($n, $k) { |
||
$n |
$n != 1 and |
||
(state @)[$k][$n] //= |
(state @)[$k][$n] //= |
||
$k == 1 ?? $n.is-prime !! |
$k == 1 ?? $n.is-prime !! |
Revision as of 23:20, 21 February 2014
Almost prime is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
A k-Almost-prime number is a natural number , that is the exact multiple of primes.
So, for example if k is 1, then this is the series of prime numbers themselves. If k is 2 then this is the series of semiprimes.
The task is to write a function/method/subroutine/... that generates k-almost primes and use it to create a table of the first ten members of k-Almost primes for .
Perl 6
Recursive implementation. Quite slow. <lang perl6>sub is-k-almost-prime($n, $k) {
$n != 1 and (state @)[$k][$n] //= $k == 1 ?? $n.is-prime !! is-k-almost-prime(
$n div (first $n %% *, grep &is-prime, 2 .. *), $k - 1
);
}
for 1 .. 5 -> $k {
say .[^10] given grep { is-k-almost-prime($_, $k) }, 2 .. *
}</lang>
- Output:
2 3 5 7 11 13 17 19 23 29 4 6 9 10 14 15 21 22 25 26 8 12 18 20 27 28 30 42 44 45 16 24 36 40 54 56 60 81 84 88 32 48 72 80 108 112 120 162 168 176
Python
This imports Prime decomposition#Python
<lang python>from prime_decomposition import decompose from itertools import islice, count try:
from functools import reduce
except:
pass
def almostprime(n, k=2):
d = decompose(n) try: terms = [d.next() for i in range(k)] return reduce(int.__mul__, terms, 1) == n except: return False
if __name__ == '__main__':
for k in range(1,6): print('%i: %r' % (k, list(islice((n for n in count() if almostprime(n, k)), 10))))</lang>
- Output:
1: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] 2: [4, 6, 9, 10, 14, 15, 21, 22, 25, 26] 3: [8, 12, 18, 20, 27, 28, 30, 42, 44, 45] 4: [16, 24, 36, 40, 54, 56, 60, 81, 84, 88] 5: [32, 48, 72, 80, 108, 112, 120, 162, 168, 176]