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
C#
<lang csharp>using System; using System.Collections.Generic; using System.Linq;
namespace AlmostPrime {
class Program { static void Main(string[] args) { foreach (int k in Enumerable.Range(1, 5)) { KPrime kprime = new KPrime() { K = k }; Console.WriteLine("k = {0}: {1}", k, string.Join<int>(" ", kprime.GetFirstN(10))); } } }
class KPrime { public int K { get; set; }
public bool IsKPrime(int number) { int primes = 0; for (int p = 2; p * p <= number && primes < K; ++p) { while (number % p == 0 && primes < K) { number /= p; ++primes; } } if (number > 1) { ++primes; } return primes == K; }
public List<int> GetFirstN(int n) { List<int> result = new List<int>(); for (int number = 2; result.Count < n; ++number) { if (IsKPrime(number)) { result.Add(number); } } return result; } }
}</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
Common Lisp
<lang lisp>(defun start ()
(loop for k from 1 to 5 do (format t "k = ~a: ~a~%" k (collect-k-almost-prime k))))
(defun collect-k-almost-prime (k &optional (d 2) (lst nil))
(cond ((= (length lst) 10) (reverse lst)) ((= (?-primality d) k) (collect-k-almost-prime k (+ d 1) (cons d lst))) (t (collect-k-almost-prime k (+ d 1) lst))))
(defun ?-primality (n &optional (d 2) (c 0))
(cond ((> d (isqrt n)) (+ c 1)) ((zerop (rem n d)) (?-primality (/ n d) d (+ c 1))) (t (?-primality n (+ d 1) c))))</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) NIL
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
ERRE
<lang ERRE> PROGRAM ALMOST_PRIME
! ! for rosettacode.org !
!$INTEGER
PROCEDURE KPRIME(N,K->KP)
LOCAL P,F FOR P=2 TO 999 DO EXIT IF NOT((F<K) AND (P*P<=N)) WHILE (N MOD P)=0 DO N/=P F+=1 END WHILE END FOR KP=(F-(N>1)=K)
END PROCEDURE
BEGIN
PRINT(CHR$(12);) !CLS FOR K=1 TO 5 DO PRINT("k =";K;":";) C=0 FOR I=2 TO 999 DO EXIT IF NOT(C<10) KPRIME(I,K->KP) IF KP THEN PRINT(I;) C+=1 END IF END FOR PRINT END FOR
END PROGRAM </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
F#
<lang fsharp>let rec genFactor (f, n) =
if f > n then None elif n % f = 0 then Some (f, (f, n/f)) else genFactor (f+1, n)
let factorsOf (num) =
Seq.unfold (fun (f, n) -> genFactor (f, n)) (2, num)
let kFactors k = Seq.unfold (fun n ->
let rec loop m = if Seq.length (factorsOf m) = k then m else loop (m+1) let next = loop n Some(next, next+1)) 2
[1 .. 5] |> List.iter (fun k ->
printfn "%A" (Seq.take 10 (kFactors k) |> Seq.toList))</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]
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]
Haskell
<lang Haskell>isPrime :: Integral a => a -> Bool isPrime n = not $ any ((0 ==) . (mod n)) [2..(truncate $ sqrt $ fromIntegral n)]
primes :: [Integer] primes = filter isPrime [2..]
isKPrime :: (Num a, Eq a) => a -> Integer -> Bool isKPrime 1 n = isPrime n isKPrime k n = any (isKPrime (k - 1)) sprimes
where sprimes = map fst $ filter ((0 ==) . snd) $ map (divMod n) $ takeWhile (< n) primes
kPrimes :: (Num a, Eq a) => a -> [Integer] kPrimes k = filter (isKPrime k) [2..]
main :: IO () main = flip mapM_ [1..5] $ \k ->
putStrLn $ "k = " ++ show k ++ ": " ++ (unwords $ map show (take 10 $ kPrimes k))</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
Larger ks require more complicated methods: <lang haskell>primes = 2:3:[n | n <- [5,7..], foldr (\p r-> p*p > n || rem n p > 0 && r) True (drop 1 primes)]
merge aa@(a:as) bb@(b:bs) | a < b = a:merge as bb | otherwise = b:merge aa bs
-- n-th item is all k-primes not divisible by any of the first n primes notdivs k = f primes $ kprimes (k-1) where f (p:ps) s = map (p*) s : f ps (filter ((/=0).(`mod`p)) s)
kprimes k | k == 1 = primes | otherwise = f (head ndk) (tail ndk) (tail $ map (^k) primes) where ndk = notdivs k -- tt is the thresholds for merging in next sequence -- it is equal to "map head seqs", but don't do that f aa@(a:as) seqs tt@(t:ts) | a < t = a : f as seqs tt | otherwise = f (merge aa $ head seqs) (tail seqs) ts
main = do -- next line is for task requirement: mapM_ (\x->print (x, take 10 $ kprimes x)) [1 .. 5]
putStrLn "\n10000th to 10100th 500-amost primes:" mapM_ print $ take 100 $ drop 10000 $ kprimes 500</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]) 10000th to 10100th 500-amost primes: 7241149198492252834202927258094752774597239286103014697435725917649659974371690699721153852986440733637405206125678822081264723636566725108094369093648384 <...snipped 99 more equally unreadable numbers...>
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 ->
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.
Java
<lang java>public class AlmostPrime {
public static void main(String args[]) { for (int k = 1; k <= 5; k++) { System.out.print("k = " + k + ":"); for (int i = 2, c = 0; c < 10; i++) if (kprime(i, k)) { System.out.print(" " + i); c++; } System.out.println(""); } }
public static boolean kprime(int n, int k) { int f = 0; for (int p = 2; f < k && p*p <= n; p++) while (0 == n % p){ n /= p; f++; } return f + ((n > 1)?1:0) == k; }
}</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
jq
Infrastructure: <lang jq># Recent versions of jq (version > 1.4) have the following definition of "until": def until(cond; next):
def _until: if cond then . else (next|_until) end; _until;
- relatively_prime(previous) tests whether the input integer is prime
- relative to the primes in the array "previous":
def relatively_prime(previous):
. as $in | (previous|length) as $plen # state: [found, ix] | [false, 0] | until( .[0] or .[1] >= $plen; [ ($in % previous[.[1]]) == 0, .[1] + 1] ) | .[0] | not ;
- Emit a stream in increasing order of all primes (from 2 onwards)
- that are less than or equal to mx:
def primes(mx):
# The helper function, next, has arity 0 for tail recursion optimization; # it expects its input to be the array of previously found primes: def next: . as $previous | ($previous | .[length-1]) as $last | if ($last >= mx) then empty else ((2 + $last) | until( relatively_prime($previous) ; . + 2)) as $nextp | if $nextp <= mx then $nextp, (( $previous + [$nextp] ) | next)
else empty
end end; if mx <= 1 then empty elif mx == 2 then 2 else (2, 3, ( [2,3] | next)) end
- Return an array of the distinct prime factors of . in increasing order
def prime_factors:
# Return an array of prime factors of . given that "primes" # is an array of relevant primes: def pf(primes): if . <= 1 then [] else . as $in | if ($in | relatively_prime(primes)) then [$in] else reduce primes[] as $p ([]; if ($in % $p) != 0 then . else . + [$p] + (($in / $p) | pf(primes))
end)
end | unique end; if . <= 1 then [] else . as $in | pf( [ primes( (1+$in) | sqrt | floor) ] ) end;
- Return an array of prime factors of . repeated according to their multiplicities:
def prime_factors_with_multiplicities:
# Emit p according to the multiplicity of p # in the input integer assuming p > 1 def multiplicity(p): if . < p then empty elif . == p then p elif (. % p) == 0 then ((./p) | recurse( if (. % p) == 0 then (. / p) else empty end) | p) else empty end;
if . <= 1 then [] else . as $in | prime_factors as $primes | if ($in|relatively_prime($primes)) then [$in] else reduce $primes[] as $p ([]; if ($in % $p) == 0 then . + [$in|multiplicity($p)] else . end ) end end;</lang>
isalmostprime <lang jq>def isalmostprime(k): (prime_factors_with_multiplicities | length) == k;
- Emit a stream of the first N almost-k primes
def almostprimes(N; k):
if N <= 0 then empty else # state [remaining, candidate, answer] [N, 1, null] | recurse( if .[0] <= 0 then empty
elif (.[1] | isalmostprime(k)) then [.[0]-1, .[1]+1, .[1]] else [.[0], .[1]+1, null]
end) | .[2] | select(. != null) end;</lang> The task:
<lang jq>range(1;6) as $k | "k=\($k): \([almostprimes(10;$k)])"</lang>
- Output:
<lang sh>$ jq -c -r -n -f Almost_prime.jq 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]</lang>
Julia
<lang julia>isalmostprime(n, k) = sum(values(factor(n))) == k function almostprimes(N, k) # return first N almost-k primes
P = Array(Int, N) i = 0; n = 2 while i < N if isalmostprime(n, k); P[i += 1] = n; end n += 1 end return P
end</lang>
- Output:
julia> [almostprimes(10, k) for k in 1:5] 5-element Array{Array{Int64,1},1}: [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]
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>
- 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
Oforth
<lang Oforth>func: kprime(n, k) { | i |
0 2 n for: i [ while(n i /mod swap 0 &==) [ ->n 1 + ] drop ] k ==
}
func: table(k) { | l |
ListBuffer new ->l 2 while (l size 10 <>) [ k over kprime ifTrue: [ dup l add ] 1 + ] drop l
}</lang>
- Output:
>5 seq apply(#[ table println ]) [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]
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,
Pascal
<lang Pascal>program AlmostPrime; {$IFDEF FPC}
{$Mode Delphi}
{$ENDIF} uses
primtrial;
var
i,K,cnt : longWord;
BEGIN
K := 1; repeat cnt := 0; i := 2; write('K=',K:2,':'); repeat if isAlmostPrime(i,K) then Begin write(i:6,' '); inc(cnt); end; inc(i); until cnt = 9; writeln; inc(k); until k > 10;
END.</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 K= 6 : 64 96 144 160 216 224 240 324 336 352 K= 7 : 128 192 288 320 432 448 480 648 672 704 K= 8 : 256 384 576 640 864 896 960 1296 1344 1408 K= 9 : 512 768 1152 1280 1728 1792 1920 2592 2688 2816 K=10 : 1024 1536 2304 2560 3456 3584 3840 5184 5376 5632
Perl
Using a CPAN module, which is simple and fast:
<lang perl>use ntheory 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>
Phix
<lang Phix> -- Naieve stuff, mostly, but coded with enthuiasm! -- Following the idea behind (but not the code from!) the J submission: -- Generate 10 primes (kept in p10) -- (print K=1) -- Multiply each of them by the first ten primes -- Sort and find unique values, take the first ten of those -- (print K=2) -- Multiply each of them by the first ten primes -- Sort and find unique values, take the first ten of those -- (print K=3) -- ... -- However I just keep a "top 10", using a bubble insertion, and stop -- multiplying as soon as everything else for p10[i] will be too big.
-- (as calculated earlier from this routine, -- or that "return 1" in pi() works just fine.) --constant f17={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59} constant f17={2,3,5,7,11,13,17}
function pi(integer n) -- approximates the number of primes less than or equal to n -- if n<=10 then return 4 end if -- -- best estimate -- return floor(n/(log(n)-1)) -- if n<=20 then return 1 end if -- (or use a table:)
if n<17 then for i=1 to length(f17) do if n<=f17[i] then return i end if end for end if
-- -- upper bound for n>=17 (Rosser and Schoenfeld 1962): -- return floor(1.25506*n/log(n))
-- lower bound for n>=17 (Rosser and Schoenfeld 1962): return floor(n/log(n))
end function
function primes(integer n) -- return the first n prime numbers (tested 0 to 20,000, which took ~86s) sequence prime integer count = 0 integer lowN, highN, midN
-- First, iteratively estimate the sieve size required lowN = 2*n highN = n*n+1 while lowN<highN do midN = floor((lowN+highN)/2) if pi(midN)>n then highN = midN else lowN = midN+1 end if end while -- Then apply standard sieve and store primes as we find -- them towards the (no longer used) start of the sieve. prime = repeat(1,highN) for i=2 to highN do if prime[i] then count += 1 prime[count] = i if count>=n then exit end if for k=i+i to highN by i do prime[k] = 0 end for end if end for return prime[1..n]
end function
procedure display(integer k, sequence kprimes)
printf(1,"%d: ",k) for i=1 to length(kprimes) do printf(1,"%5d",kprimes[i]) end for puts(1,"\n")
end procedure
function bubble(sequence next, integer v) -- insert v into next (discarding next[$]), keeping next in ascending order -- (relies on next[1] /always/ being smaller that anything that we insert.)
for i=length(next)-1 to 1 by -1 do if v>next[i] then next[i+1] = v exit end if next[i+1] = next[i] end for return next
end function
procedure almost_prime() sequence p10 = primes(10) sequence apk = p10 -- (almostprime[k]) sequence next = repeat(0,length(p10)) integer high, test
for k=1 to 5 do display(k,apk) if k=5 then exit end if next = apk for i=1 to length(p10) do
-- next[i] = apk[i]*p10[1]
next[i] = apk[i]*2 end for high = next[$] for i=2 to length(p10) do for j=1 to length(next) do test = apk[j]*p10[i] if not find(test,next) then if test>high then exit end if next = bubble(next,test) high = next[$] end if end for end for apk = next end for if getc(0) then end if
end procedure
almost_prime()
</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
and a translation of the C version, with improved variable names and some extra notes <lang Phix>
function kprime(integer n, integer k) -- -- returns true if n has exactly k factors -- -- p is a "pseudo prime" in that 2,3,4,5,6,7,8,9,10,11 will behave -- exactly like 2,3,5,7,11, ie the remainder(n,4)=0 (etc) will never -- succeed because remainder(n,2) would have succeeded twice first. -- Hence for larger n consider replacing p+=1 with p=next_prime(), -- then again, on "" this performs an obscene number of divisions.. -- integer p = 2,
factors = 0
while factors<k and p*p<=n do while remainder(n,p)=0 do n = n/p factors += 1 end while p += 1 end while factors += (n>1) return factors==k
end function
procedure almost_primeC() integer nextkprime, count
for k=1 to 5 do printf(1,"k = %d: ", k); nextkprime = 2 count = 0 while count<10 do if kprime(nextkprime, k) then printf(1," %4d", nextkprime) count += 1 end if nextkprime += 1 end while puts(1,"\n") end for if getc(0) then end if
end procedure
almost_primeC()
</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
PicoLisp
<lang PicoLisp>(de factor (N)
(make (let (D 2 L (1 2 2 . (4 2 4 2 4 6 2 6 .)) M (sqrt N) ) (while (>= M D) (if (=0 (% N D)) (setq M (sqrt (setq N (/ N (link D)))) ) (inc 'D (pop 'L)) ) ) (link N) ) ) )
(de almost (N)
(let (X 2 Y 0) (make (loop (when (and (nth (factor X) N) (not (cdr @))) (link X) (inc 'Y) ) (T (= 10 Y) 'done) (inc 'X) ) ) ) )
(for I 5
(println I '-> (almost I) ) )
(bye)</lang>
Potion
<lang potion># Converted from C kprime = (n, k):
p = 2, f = 0 while (f < k && p*p <= n): while (0 == n % p): n /= p f++. p++. n = if (n > 1): 1. else: 0. f + n == k.
1 to 5 (k):
"k = " print, k print, ":" print i = 2, c = 0 while (c < 10): if (kprime(i, k)): " " print, i print, c++. i++ . "" say.</lang>
C and Potion take 0.006s, Perl5 0.028s
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
count factors
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
count factors with limit
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]
Rust
<lang rust>fn is_kprime(n: usize, k: usize) -> bool { let mut primes = 0us; let mut f = 2us; let mut rem = n; while primes < k && rem > 1{ while (rem % f) == 0 && rem > 1{ rem /= f; primes += 1; } f += 1; } rem == 1 && primes == k }
struct KPrimeGen { k: usize, n: usize, }
impl Iterator for KPrimeGen { type Item = usize; fn next(&mut self) -> Option<usize> { self.n += 1; while !is_kprime(self.n, self.k) { self.n += 1; } Some(self.n) } }
fn kprime_generator(k: usize) -> KPrimeGen { KPrimeGen {k: k, n: 1} }
fn main() { for k in 1us..6 { println!("{}: {:?}", k, kprime_generator(k).take(10).collect::<Vec<_>>()); } } </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]
Scala
<lang Scala>def isKPrime(n: Int, k: Int, d: Int = 2): Boolean = (n, k, d) match {
case (n, k, _) if n == 1 => k == 0 case (n, _, d) if n % d == 0 => isKPrime(n / d, k - 1, d) case (_, _, _) => isKPrime(n, k, d + 1)
}
def kPrimeStream(k: Int): Stream[Int] = {
def loop(n: Int): Stream[Int] = if (isKPrime(n, k)) n #:: loop(n+ 1) else loop(n + 1) loop(2)
}
for (k <- 1 to 5) {
println( s"$k: [${ kPrimeStream(k).take(10) mkString " " }]" )
}</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]
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
zkl
Using the prime generator from task Extensible prime generator#zkl.
Can't say I entirely understand this algorithm. Uses list comprehension to calculate the outer/tensor product (p10 ⊗ ar). <lang zkl>primes:=Utils.Generator(Import("sieve").postponed_sieve); (p10:=ar:=primes.walk(10)).println(); do(4){
(ar=((x,y);ar;p10;'* : Utils.Helpers.listUnique(_).sort()[0,10])).println();
}</lang>
- Output:
L(2,3,5,7,11,13,17,19,23,29) L(4,6,9,10,14,15,21,22,25,26) L(8,12,18,20,27,28,30,42,44,45) L(16,24,36,40,54,56,60,81,84,88) L(32,48,72,80,108,112,120,162,168,176)