Almost prime: Difference between revisions
(→{{header|REXX}}: added the REXX language. -- ~~~~) |
m (→{{header|REXX}}: changed/added comments, changed the wording in the output. -- ~~~~) |
||
Line 72: | Line 72: | ||
$=$ j /*append k-almost prime to list. */ |
$=$ j /*append k-almost prime to list. */ |
||
end /*j*/ /* [↑] gen N k-almost primes.*/ |
end /*j*/ /* [↑] gen N k-almost primes.*/ |
||
say ' |
say N ' ' i"-almost primes:" $ /*display the k-almost primes. */ |
||
end /*i*/ |
end /*i*/ /* [↑] display a line for each K*/ |
||
exit /*stick a fork in it, we're done.*/ |
exit /*stick a fork in it, we're done.*/ |
||
/*──────────────────────────────────FACTR subroutine────────────────────*/ |
/*──────────────────────────────────FACTR subroutine────────────────────*/ |
||
Line 84: | Line 84: | ||
if j>z then leave /*# reduced to a small number? */ |
if j>z then leave /*# reduced to a small number? */ |
||
call .factr /*add a factor to factor count. */ |
call .factr /*add a factor to factor count. */ |
||
end /*y*/ /* [↑] find all factors in X. */ |
|||
end /*y*/ |
|||
if f==0 then return 1 /*return 1 if the number is prime*/ |
if f==0 then return 1 /*return 1 if the number is prime*/ |
||
return f /*otherwise, return the # factors*/ |
return f /*otherwise, return the # factors*/ |
||
Line 91: | Line 91: | ||
if z//j\==0 then return /*can't divide any more? */ |
if z//j\==0 then return /*can't divide any more? */ |
||
f=f+1 /*bump the factor count. */ |
f=f+1 /*bump the factor count. */ |
||
z=z%j /*do an integer divide. |
z=z%j /*do an (%) integer divide. */ |
||
end /*forever*/</lang> |
end /*forever*/</lang> |
||
'''output''' when using the default input: |
'''output''' when using the default input: |
||
<pre> |
<pre> |
||
10 1-almost primes: 2 3 5 7 11 13 17 19 23 29 |
|||
10 2-almost primes: 4 6 9 10 14 15 21 22 25 26 |
|||
10 3-almost primes: 8 12 18 20 27 28 30 42 44 45 |
|||
10 4-almost primes: 16 24 36 40 54 56 60 81 84 88 |
|||
10 5-almost primes: 32 48 72 80 108 112 120 162 168 176 |
|||
</pre> |
</pre> |
Revision as of 01:20, 22 February 2014
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]
REXX
<lang rexx>/*REXX program displays the N numbers of the first K k-almost primes*/ parse arg N K . /*get the arguments from the C.L.*/ if N== then N=10 /*No N? Then use the default.*/ if K== then K=5 /* " K? " " " " */
/* [↓] generate one line per K.*/ do i=1 for K; $= /*generate K k-almost primes. */ #=0 /*number of k-almost primes found*/ do j=1 until #==N /*process an almost-prime N times*/ if factr(j)\==i then iterate /*not the correct k-almost prime?*/ #=#+1 /*bump the k-almost prime counter*/ $=$ j /*append k-almost prime to list. */ end /*j*/ /* [↑] gen N k-almost primes.*/ say N ' ' i"-almost primes:" $ /*display the k-almost primes. */ end /*i*/ /* [↑] display a line for each K*/
exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────FACTR subroutine────────────────────*/ factr: procedure; parse arg x 1 z; f=0 /*defines X and Z to the arg.*/ if x<2 then return 0 /*invalid number? Then return 0.*/
do j=2 to 5; if j\==4 then call .factr; end /*fast factoring.*/
j=5 /*start were we left off (J=5). */
do y=0 by 2; j=j+2+y//4 /*insure it's not divisible by 3.*/ if right(j,1)==5 then iterate /*fast check for divisible by 5.*/ if j>z then leave /*# reduced to a small number? */ call .factr /*add a factor to factor count. */ end /*y*/ /* [↑] find all factors in X. */
if f==0 then return 1 /*return 1 if the number is prime*/
return f /*otherwise, return the # factors*/
/*──────────────────────────────────.FACTR subroutine───────────────────*/ .factr: do forever /*keep dividing until it hurts. */
if z//j\==0 then return /*can't divide any more? */ f=f+1 /*bump the factor count. */ z=z%j /*do an (%) integer divide. */ end /*forever*/</lang>
output when using the default input:
10 1-almost primes: 2 3 5 7 11 13 17 19 23 29 10 2-almost primes: 4 6 9 10 14 15 21 22 25 26 10 3-almost primes: 8 12 18 20 27 28 30 42 44 45 10 4-almost primes: 16 24 36 40 54 56 60 81 84 88 10 5-almost primes: 32 48 72 80 108 112 120 162 168 176