Almost prime
You are encouraged to solve this task according to the task description, using any language you may know.
A k-Almost-prime is a natural number that is the product of (possibly identical) primes. So, for example, 1-almost-primes, where , are the prime numbers themselves; 2-almost-primes are the semiprimes.
The task is to write a function/method/subroutine/... that generates k-almost primes and use it to create a table here of the first ten members of k-Almost primes for .
- Cf.
Ada
This imports the package Prime_Numbers from Prime decomposition#Ada.
<lang ada>with Prime_Numbers, Ada.Text_IO;
procedure Test_Kth_Prime is
package Integer_Numbers is new
Prime_Numbers (Natural, 0, 1, 2);
use Integer_Numbers;
Out_Length: constant Positive := 10; -- 10 k-th almost primes
N: Positive; -- the "current number" to be checked
begin
for K in 1 .. 5 loop
Ada.Text_IO.Put("K =" & Integer'Image(K) &": ");
N := 2;
for I in 1 .. Out_Length loop
while Decompose(N)'Length /= K loop N := N + 1; end loop; -- now N is Kth almost prime; Ada.Text_IO.Put(Integer'Image(Integer(N))); N := N + 1;
end loop;
Ada.Text_IO.New_Line;
end loop;
end Test_Kth_Prime;</lang>
- Output:
K = 1: 2 3 5 7 11 13 17 19 23 29 K = 2: 4 6 9 10 14 15 21 22 25 26 K = 3: 8 12 18 20 27 28 30 42 44 45 K = 4: 16 24 36 40 54 56 60 81 84 88 K = 5: 32 48 72 80 108 112 120 162 168 176
AutoHotkey
Translation of the C Version <lang AutoHotkey>kprime(n,k) { p:=2, f:=0 while( (f<k) && (p*p<=n) ) { while ( 0==mod(n,p) ) { n/=p f++ } p++ } return f + (n>1) == k }
k:=1, results:="" while( k<=5 ) { i:=2, c:=0, results:=results "k =" k ":" while( c<10 ) { if (kprime(i,k)) { results:=results " " i c++ } i++ } results:=results "`n" k++ }
MsgBox % results</lang>
Output (Msgbox):
k =1: 2 3 5 7 11 13 17 19 23 29 k =2: 4 6 9 10 14 15 21 22 25 26 k =3: 8 12 18 20 27 28 30 42 44 45 k =4: 16 24 36 40 54 56 60 81 84 88 k =5: 32 48 72 80 108 112 120 162 168 176
C
<lang c>#include <stdio.h>
int kprime(int n, int k) { int p, f = 0; for (p = 2; f < k && p*p <= n; p++) while (0 == n % p) n /= p, f++;
return f + (n > 1) == k; }
int main(void) { int i, c, k;
for (k = 1; k <= 5; k++) { printf("k = %d:", k);
for (i = 2, c = 0; c < 10; i++) if (kprime(i, k)) { printf(" %d", i); c++; }
putchar('\n'); }
return 0; }</lang>
- Output:
k = 1: 2 3 5 7 11 13 17 19 23 29 k = 2: 4 6 9 10 14 15 21 22 25 26 k = 3: 8 12 18 20 27 28 30 42 44 45 k = 4: 16 24 36 40 54 56 60 81 84 88 k = 5: 32 48 72 80 108 112 120 162 168 176
D
This contains a copy of the function decompose from the Prime decomposition task.
<lang d>import std.stdio, std.algorithm, std.traits;
Unqual!T[] decompose(T)(in T number) pure nothrow in {
assert(number > 1);
} body {
typeof(return) result; Unqual!T n = number;
for (Unqual!T i = 2; n % i == 0; n /= i)
result ~= i;
for (Unqual!T i = 3; n >= i * i; i += 2)
for (; n % i == 0; n /= i)
result ~= i;
if (n != 1)
result ~= n;
return result;
}
void main() {
enum outLength = 10; // 10 k-th almost primes.
foreach (immutable k; 1 .. 6) {
writef("K = %d: ", k);
auto n = 2; // The "current number" to be checked.
foreach (immutable i; 1 .. outLength + 1) {
while (n.decompose.length != k)
n++;
// Now n is K-th almost prime.
write(n, " ");
n++;
}
writeln;
}
}</lang>
- Output:
K = 1: 2 3 5 7 11 13 17 19 23 29 K = 2: 4 6 9 10 14 15 21 22 25 26 K = 3: 8 12 18 20 27 28 30 42 44 45 K = 4: 16 24 36 40 54 56 60 81 84 88 K = 5: 32 48 72 80 108 112 120 162 168 176
Go
<lang go>package main
import "fmt"
func kPrime(n, k int) bool {
nf := 0
for i := 2; i <= n; i++ {
for n%i == 0 {
if nf == k {
return false
}
nf++
n /= i
}
}
return nf == k
}
func gen(k, n int) []int {
r := make([]int, n)
n = 2
for i := range r {
for !kPrime(n, k) {
n++
}
r[i] = n
n++
}
return r
}
func main() {
for k := 1; k <= 5; k++ {
fmt.Println(k, gen(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]
Objeck
<lang objeck>class Kth_Prime {
function : native : kPrime(n : Int, k : Int) ~ Bool {
f := 0;
for (p := 2; f < k & p*p <= n; p+=1;) {
while (0 = n % p) {
n /= p; f+=1;
};
};
return f + ((n > 1) ? 1 : 0) = k;
}
function : Main(args : String[]) ~ Nil {
for (k := 1; k <= 5; k+=1;) {
"k = {$k}:"->Print();
c := 0;
for (i := 2; c < 10; i+=1;) {
if (kPrime(i, k)) {
" {$i}"->Print();
c+=1;
};
};
'\n'->Print();
};
}
}</lang>
- Output:
k = 1: 2 3 5 7 11 13 17 19 23 29 k = 2: 4 6 9 10 14 15 21 22 25 26 k = 3: 8 12 18 20 27 28 30 42 44 45 k = 4: 16 24 36 40 54 56 60 81 84 88 k = 5: 32 48 72 80 108 112 120 162 168 176
Icon and Unicon
Works in both languages. <lang unicon>link "factors"
procedure main()
every writes(k := 1 to 5,": ") do
every writes(right(genKap(k),5)\10|"\n")
end
procedure genKap(k)
suspend (k = *factors(n := seq(q)), n)
end</lang>
Output:
->ap
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
->
=={{header|J}}==
<lang J> (10 {. [:~.[:/:~[:,*/~)^:(i.5)~p:i.10
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</lang>
Explanation:
#Generate 10 primes.
#Multiply each of them by the first ten primes
#Sort and find unique values, take the first ten of those
#Multiply each of them by the first ten primes
#Sort and find unique values, take the first ten of those
:...
The results of the odd steps in this procedure are the desired result.
=={{header|Mathematica}}==
<lang Mathematica>kprimes[k_,n_] :=
(* generates a list of the n smallest k-almost-primes *)
Module[{firstnprimes, runningkprimes = {}},
firstnprimes = Prime[Range[n]];
runningkprimes = firstnprimes;
Do[
runningkprimes =
Outer[Times, firstnprimes , runningkprimes ] // Flatten // Union // Take[#, n] & ;
(* only keep lowest n numbers in our running list *)
, {i, 1, k - 1}];
runningkprimes
]
(* now to create table with n=10 and k ranging from 1 to 5 *)
Table[Flatten[{"k = " <> ToString[i] <> ": ", kprimes[i, 10]}], {i,1,5}] // TableForm</lang>
{{out}}
<pre>k = 1: 2 3 5 7 11 13 17 19 23 29
k = 2: 4 6 9 10 14 15 21 22 25 26
k = 3: 8 12 18 20 27 28 30 42 44 45
k = 4: 16 24 36 40 54 56 60 81 84 88
k = 5: 32 48 72 80 108 112 120 162 168 176
PARI/GP
<lang parigp>almost(k)=my(n); for(i=1,10,while(bigomega(n++)!=k,); print1(n", ")); for(k=1,5,almost(k);print)</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,
Perl
Using a CPAN module, which is simple and fast: <lang perl>use Math::Prime::Util qw/factor/; sub almost {
my($k,$n) = @_;
my $i = 1;
map { $i++ while scalar factor($i) != $k; $i++ } 1..$n;
} say "$_ : ", join(" ", almost($_,10)) for 1..5;</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
or writing everything by hand: <lang perl>use strict; use warnings;
sub k_almost_prime;
for my $k ( 1 .. 5 ) { my $almost = 0; print join(", ", map { 1 until k_almost_prime ++$almost, $k; "$almost"; } 1 .. 10), "\n"; }
sub nth_prime;
sub k_almost_prime { my ($n, $k) = @_; return if $n <= 1 or $k < 1; my $which_prime = 0; for my $count ( 1 .. $k ) { while( $n % nth_prime $which_prime ) { ++$which_prime; } $n /= nth_prime $which_prime; return if $n == 1 and $count != $k; } ($n == 1) ? 1 : (); }
BEGIN { # This is loosely based on one of the python solutions # to the RC Sieve of Eratosthenes task. my @primes = (2, 3, 5, 7); my $p_iter = 1; my $p = $primes[$p_iter]; my $q = $p*$p; my %sieve; my $candidate = $primes[-1] + 2; sub nth_prime { my $n = shift; return if $n < 0; OUTER: while( $#primes < $n ) { while( my $s = delete $sieve{$candidate} ) { my $next = $s + $candidate; $next += $s while exists $sieve{$next}; $sieve{$next} = $s; $candidate += 2; } while( $candidate < $q ) { push @primes, $candidate; $candidate += 2; next OUTER if exists $sieve{$candidate}; } my $twop = 2 * $p; my $next = $q + $twop; $next += $twop while exists $sieve{$next}; $sieve{$next} = $twop; $p = $primes[++$p_iter]; $q = $p * $p; $candidate += 2; } return $primes[$n]; } }</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
Perl 6
<lang perl6>sub is-k-almost-prime($n is copy, $k) returns Bool {
loop (my ($p, $f) = 2, 0; $f < $k && $p*$p <= $n; $p++) {
$n /= $p, $f++ while $n %% $p;
}
$f + ($n > 1) == $k;
}
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
Here is a solution with identical output based on the factors routine from Count_in_factors#Perl_6 (to be included manually until we decide where in the distribution to put it). <lang perl6>constant factory = 0..* Z=> (0, 0, map { +factors($_) }, 2..*);
sub almost($n) { map *.key, grep *.value == $n, factory }
say almost($_)[^10] for 1..5;</lang>
Prolog
<lang prolog>% almostPrime(K, +Take, List) succeeds if List can be unified with the % first Take K-almost-primes. % Notice that K need not be specified. % To avoid having to cache or recompute the first Take primes, we define % almostPrime/3 in terms of almostPrime/4 as follows: % almostPrime(K, Take, List) :-
% Compute the list of the first Take primes: nPrimes(Take, Primes), almostPrime(K, Take, Primes, List).
almostPrime(1, Take, Primes, Primes).
almostPrime(K, Take, Primes, List) :-
generate(2, K), % generate K >= 2 K1 is K - 1, almostPrime(K1, Take, Primes, L), multiplylist( Primes, L, Long), sort(Long, Sorted), % uniquifies take(Take, Sorted, List).
</lang>That's it. The rest is machinery. For portability, a compatibility section is included below. <lang Prolog>nPrimes( M, Primes) :- nPrimes( [2], M, Primes).
nPrimes( Accumulator, I, Primes) :- next_prime(Accumulator, Prime), append(Accumulator, [Prime], Next), length(Next, N), ( N = I -> Primes = Next; nPrimes( Next, I, Primes)).
% next_prime(+Primes, NextPrime) succeeds if NextPrime is the next % prime after a list, Primes, of consecutive primes starting at 2. next_prime([2], 3). next_prime([2|Primes], P) :- last(Primes, PP), P2 is PP + 2, generate(P2, N), 1 is N mod 2, % odd Max is floor(sqrt(N+1)), % round-off paranoia forall( (member(Prime, [2|Primes]), (Prime =< Max -> true ; (!, fail))), N mod Prime > 0 ), !,
P = N.
% multiply( +A, +List, Answer ) multiply( A, [], [] ). multiply( A, [X|Xs], [AX|As] ) :-
AX is A * X, multiply(A, Xs, As).
% multiplylist( L1, L2, List ) succeeds if List is the concatenation of X * L2 % for successive elements X of L1. multiplylist( [], B, [] ). multiplylist( [A|As], B, List ) :-
multiply(A, B, L1), multiplylist(As, B, L2), append(L1, L2, List).
take(N, List, Head) :-
length(Head, N), append(Head,X,List).
</lang> <lang Prolog>%%%%% compatibility section %%%%%
- - if(current_prolog_flag(dialect, yap)).
generate(Min, I) :- between(Min, inf, I).
append([],L,L). append([X|Xs], L, [X|Ls]) :- append(Xs,L,Ls).
- - endif.
- - if(current_prolog_flag(dialect, swi)).
generate(Min, I) :- between(Min, inf, I).
- - endif.
- - if(current_prolog_flag(dialect, yap)).
append([],L,L). append([X|Xs], L, [X|Ls]) :- append(Xs,L,Ls).
last([X], X). last([_|Xs],X) :- last(Xs,X).
- - endif.
- - if(current_prolog_flag(dialect, gprolog)).
generate(Min, I) :-
current_prolog_flag(max_integer, Max), between(Min, Max, I).
- - endif.
</lang>
Example using SWI-Prolog:
?- between(1,5,I), (almostPrime(I, 10, L) -> writeln(L)), fail. [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] ?- time( (almostPrime(5, 10, L), writeln(L))). [32,48,72,80,108,112,120,162,168,176] % 1,906 inferences, 0.001 CPU in 0.001 seconds (84% CPU, 2388471 Lips)
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 = [next(d) 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]
Racket
<lang racket>#lang racket (require (only-in math/number-theory factorize))
(define ((k-almost-prime? k) n)
(= k (for/sum ((f (factorize n))) (cadr f))))
(define KAP-table-values
(for/list ((k (in-range 1 (add1 5))))
(define kap? (k-almost-prime? k))
(for/list ((j (in-range 10)) (i (sequence-filter kap? (in-naturals 1))))
i)))
(define (format-table t)
(define longest-number-length
(add1 (order-of-magnitude (argmax order-of-magnitude (cons (length t) (apply append t))))))
(define (fmt-val v) (~a v #:width longest-number-length #:align 'right))
(string-join
(for/list ((r t) (k (in-naturals 1)))
(string-append
(format "║ k = ~a║ " (fmt-val k))
(string-join (for/list ((c r)) (fmt-val c)) "| ")
"║"))
"\n"))
(displayln (format-table KAP-table-values))</lang>
- Output:
║ k = 1║ 2| 3| 5| 7| 11| 13| 17| 19| 23| 29║ ║ k = 2║ 4| 6| 9| 10| 14| 15| 21| 22| 25| 26║ ║ k = 3║ 8| 12| 18| 20| 27| 28| 30| 42| 44| 45║ ║ k = 4║ 16| 24| 36| 40| 54| 56| 60| 81| 84| 88║ ║ k = 5║ 32| 48| 72| 80| 108| 112| 120| 162| 168| 176║
REXX
version 1
The method used is to count the number of factors in the number to determine the K-primality.
The first two k-almost primes are computed directly.
<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? " " " " */
/* [↓] display one line per K.*/
do m=1 for K; $=2**m; fir=$ /*generate the 1st k_almost prime*/
#=1; if #==N then leave /*# k-almost primes; 'nuff found?*/
sec=3*(2**(m-1)); $=$ sec; #=2 /*generate the 2nd k-almost prime*/
do j=fir+fir+1 until #==N /*process an almost-prime N times*/
if #factr(j)\==m 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 right(m,4)"-almost primes:" $ /*display the k-almost primes.*/
end /*m*/ /* [↑] 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 /*number reduced to a wee number?*/ call .#factr /*go add other factors to count. */ end /*y*/ /* [↑] find all factors in X. */
return max(f,1) /*if prime (f==0), then return 1.*/ /*──────────────────────────────────.#FACTR subroutine──────────────────*/ .#factr: do f=f+1 while z//j==0 /*keep dividing until we can't. */
z=z%j /*perform an (%) integer divide.*/
end /*while*/ /* [↑] whittle down the Z num.*/
f=f-1 /*adjust the count of factors. */ return</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
version 2
The method used is practically identical to version 1, but the factoring stops if the number of factors exceeds the goal. The first two k-almost primes are computed directly. <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? " " " " */
/* [↓] display one line per K.*/
do m=1 for K; $=2**m; fir=$ /*generate the 1st k_almost prime*/
#=1; if #==N then leave /*# k-almost primes; 'nuff found?*/
sec=3*(2**(m-1)); $=$ sec; #=2 /*generate the 2nd k-almost prime*/
do j=fir+fir+1 until #==N /*process an almost-prime N times*/
if #factL(j,m)\==m 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 right(m,4)"-almost primes:" $ /*display the k-almost primes.*/
end /*m*/ /* [↑] display a line for each K*/
exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────#FACTL subroutine───────────────────*/
- factL: procedure; parse arg x 1 z,L /*defines X and Z to the arg.*/
f=0; if x<2 then return 0 /*invalid number? Then return 0.*/
do j=2 to 5; if j\==4 then call .#factL; end /*fast factoring.*/
if f>L then return f /*#factors > L ? Then too many.*/ 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 /*number reduced to a wee number?*/ call .#factL /*go add other factors to count. */ if f>L then return f /*#factors > L ? Then too many.*/ end /*y*/ /* [↑] find all factors in X. */
return max(f,1) /*if prime (f==0), then return 1.*/ /*──────────────────────────────────.#FACTL subroutine──────────────────*/ .#factL: do f=f+1 while z//j==0 /*keep dividing until we can't. */
z=z%j /*perform an (%) integer divide.*/
end /*while*/ /* [↑] whittle down the Z num.*/
f=f-1 /*adjust the count of factors. */ return</lang> output when using the input of: 20 12
20 1-almost primes: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 20 2-almost primes: 4 6 9 10 14 15 21 22 25 26 33 34 35 38 39 46 49 51 55 57 20 3-almost primes: 8 12 18 20 27 28 30 42 44 45 50 52 63 66 68 70 75 76 78 92 20 4-almost primes: 16 24 36 40 54 56 60 81 84 88 90 100 104 126 132 135 136 140 150 152 20 5-almost primes: 32 48 72 80 108 112 120 162 168 176 180 200 208 243 252 264 270 272 280 300 20 6-almost primes: 64 96 144 160 216 224 240 324 336 352 360 400 416 486 504 528 540 544 560 600 20 7-almost primes: 128 192 288 320 432 448 480 648 672 704 720 800 832 972 1008 1056 1080 1088 1120 1200 20 8-almost primes: 256 384 576 640 864 896 960 1296 1344 1408 1440 1600 1664 1944 2016 2112 2160 2176 2240 2400 20 9-almost primes: 512 768 1152 1280 1728 1792 1920 2592 2688 2816 2880 3200 3328 3888 4032 4224 4320 4352 4480 4800 20 10-almost primes: 1024 1536 2304 2560 3456 3584 3840 5184 5376 5632 5760 6400 6656 7776 8064 8448 8640 8704 8960 9600 20 11-almost primes: 2048 3072 4608 5120 6912 7168 7680 10368 10752 11264 11520 12800 13312 15552 16128 16896 17280 17408 17920 19200 20 12-almost primes: 4096 6144 9216 10240 13824 14336 15360 20736 21504 22528 23040 25600 26624 31104 32256 33792 34560 34816 35840 38400
Ruby
<lang ruby>require 'prime'
def almost_primes(k=2)
return to_enum(:almost_primes, k) unless block_given? n = 0 loop do n += 1 yield n if n.prime_division.map( &:last ).inject( &:+ ) == k end
end
(1..5).each{|k| puts almost_primes(k).take(10).join(", ")}</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
<lang ruby>require 'prime'
p ar = pr = Prime.take(10) 4.times{p ar = ar.product(pr).map{|(a,b)| a*b}.uniq.sort.take(10)}</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]
Tcl
<lang tcl>package require Tcl 8.6 package require math::numtheory
proc firstNprimes n {
for {set result {};set i 2} {[llength $result] < $n} {incr i} {
if {[::math::numtheory::isprime $i]} { lappend result $i }
} return $result
}
proc firstN_KalmostPrimes {n k} {
set p [firstNprimes $n]
set i [lrepeat $k 0]
set c {}
while true {
dict set c [::tcl::mathop::* {*}[lmap j $i {lindex $p $j}]] "" for {set x 0} {$x < $k} {incr x} { lset i $x [set xx [expr {([lindex $i $x] + 1) % $n}]] if {$xx} break } if {$x == $k} break
}
return [lrange [lsort -integer [dict keys $c]] 0 [expr {$n - 1}]]
}
for {set K 1} {$K <= 5} {incr K} {
puts "$K => [firstN_KalmostPrimes 10 $K]"
}</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