A k-Almost-prime is a natural number that is the product of (possibly identical) primes.
1-almost-primes, where , are the prime numbers themselves.
2-almost-primes, where , are the semiprimes.
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 .
F k_prime(k, =n) V f = 0 V p = 2 L f < k & p * p <= n L n % p == 0 n /= p f++ p++ R f + (I n > 1 {1} E 0) == kF primes(k, n) V i = 2 [Int] list L list.len < n I k_prime(k, i) list [+]= i i++ R listL(k) 1..5 print(‘k = ’k‘: ’primes(k, 10))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]
BYTE FUNC IsAlmostPrime(INT num BYTE k) INT f,p,v f=0 p=2 v=num WHILE f<k AND p*p<=num DO WHILE v MOD p=0 DO v==/p f==+1 OD p==+1 OD IF v>1 THEN f==+1 FI IF f=k THEN RETURN (1) FIRETURN (0)PROC Main() BYTE count,k INT i FOR k=1 TO 5 DO PrintF("k=%B:",k) count=0 i=2 WHILE count<10 DO IF IsAlmostPrime(i,k) THEN PrintF(" %I",i) count==+1 FI i==+1 OD PutE() ODRETURNScreenshot from Atari 8-bit computer
k=1: 2 3 5 7 11 13 17 19 23 29k=2: 4 6 9 10 14 15 21 22 25 26k=3: 8 12 18 20 27 28 30 42 44 45k=4: 16 24 36 40 54 56 60 81 84 88k=5: 32 48 72 80 108 112 120 162 168 176
This imports the packagePrime_Numbers fromPrime decomposition#Ada.
withPrime_Numbers,Ada.Text_IO;procedureTest_Kth_PrimeispackageInteger_Numbersis newPrime_Numbers(Natural, 0, 1, 2);useInteger_Numbers;Out_Length:constantPositive:=10;-- 10 k-th almost primesN:Positive;-- the "current number" to be checkedbeginforKin1..5loopAda.Text_IO.Put("K ="&Integer'Image(K)&": ");N:=2;forIin1..Out_LengthloopwhileDecompose(N)'Length/=KloopN:=N+1;endloop;-- now N is Kth almost prime;Ada.Text_IO.Put(Integer'Image(Integer(N)));N:=N+1;endloop;Ada.Text_IO.New_Line;endloop;endTest_Kth_Prime;
K = 1: 2 3 5 7 11 13 17 19 23 29K = 2: 4 6 9 10 14 15 21 22 25 26K = 3: 8 12 18 20 27 28 30 42 44 45K = 4: 16 24 36 40 54 56 60 81 84 88K = 5: 32 48 72 80 108 112 120 162 168 176
Tested with Agena 6.3.4 Win32
scope # show some k-almost-primes - translation of C via Algol W local proc kPrime( nv :: number, k :: number ) :: boolean local p, f, n := 3, 0, nv; while f <= k and n mod 2 = 0 do n \:= 2; f +:= 1 od; while f <= k and p * p <= n do while n mod p = 0 do n \:= p; f +:= 1 od; p +:= 2 od; if n > 1 then f +:= 1 fi; return f = k end; scope # task for k to 5 do printf( "k = %d: ", k ); local c, i := 0, 2; while c < 10 do if kPrime( i, k ) then printf( " %3d", i ); c +:= 1 fi; i +:= 1 od; print() od epocsepocs
k = 1: 2 3 5 7 11 13 17 19 23 29k = 2: 4 6 9 10 14 15 21 22 25 26k = 3: 8 12 18 20 27 28 30 42 44 45k = 4: 16 24 36 40 54 56 60 81 84 88k = 5: 32 48 72 80 108 112 120 162 168 176
Worth noticing is the n(...)(...) picture in the printf and the WHILE ... DO SKIP OD idiom which is quite common in ALgol 68.
BEGIN INT examples=10, classes=5; MODE SEMIPRIME = STRUCT ([examples]INT data, INT count); [classes]SEMIPRIME semi primes; PROC num facs = (INT n) INT :COMMENT Return number of not necessarily distinct prime factors of n. Not very efficient for large n ...COMMENT BEGIN INT tf := 2, residue := n, count := 1; WHILE tf < residue DO INT remainder = residue MOD tf; ( remainder = 0 | count +:= 1; residue %:= tf | tf +:= 1 ) OD; count END; PROC update table = (REF []SEMIPRIME table, INT i) BOOL :COMMENT Add i to the appropriate row of the table, if any, unless that row is already full. Return a BOOL which is TRUE when all of the table is full.COMMENT BEGIN INT k := num facs(i); IF k <= classes THEN INT c = 1 + count OF table[k]; ( c <= examples | (data OF table[k])[c] := i; count OF table[k] := c ) FI; INT sum := 0; FOR i TO classes DO sum +:= count OF table[i] OD; sum < classes * examples END; FOR i TO classes DO count OF semi primes[i] := 0 OD; FOR i FROM 2 WHILE update table (semi primes, i) DO SKIP OD; FOR i TO classes DO printf (($"k = ", d, ":", n(examples)(xg(0))l$, i, data OF semi primes[i])) ODEND
k = 1: 2 3 5 7 11 13 17 19 23 29k = 2: 4 6 9 10 14 15 21 22 25 26k = 3: 8 12 18 20 27 28 30 42 44 45k = 4: 16 24 36 40 54 56 60 81 84 88k = 5: 32 48 72 80 108 112 120 162 168 176
begininteger function mod(a, b);integer a, b;mod := a-(a/b)*b;integer function kprime(n, k);integer n, k;begin integer p, f; f := 0; p := 2; while f < k and p*p <= n do begin while mod(n,p) = 0 do begin n := n / p; f := f + 1; end; p := p + 1; end; if n > 1 then f := f + 1; if f = k then kprime := 1 else kprime := 0;end;integer i, c, k;for k := 1 step 1 until 5 dobegin write("k ="); writeon(k); writeon(": "); c := 0; i := 2; while c < 10 do begin if kprime(i, k) <> 0 then begin writeon(i); c := c + 1; end; i := i + 1; end;end;endk = 1: 2 3 5 7 11 13 17 19 23 29k = 2: 4 6 9 10 14 15 21 22 25 26k = 3: 8 12 18 20 27 28 30 42 44 45k = 4: 16 24 36 40 54 56 60 81 84 88k = 5: 32 48 72 80 108 112 120 162 168 176
with tweaks to the factorisation routine.
begin logical procedure kPrime( integer value nv, k ) ; begin integer p, f, n; n := nv; f := 0; while f <= k and not odd( n ) do begin n := n div 2; f := f + 1 end while_not_odd_n ; p := 3; while f <= k and p * p <= n do begin while n rem p = 0 do begin n := n div p; f := f + 1 end while_n_rem_p_eq_0 ; p := p + 2 end while_f_le_k_and_p_is_a_factor ; if n > 1 then f := f + 1; f = k end kPrime ; begin for k := 1 until 5 do begin integer c, i; write( i_w := 1, s_w := 0, "k = ", k , ": " ); c := 0; i := 2; while c < 10 do begin if kPrime( i, k ) then begin writeon( i_w := 3, s_w := 0, " ", i ); c := c + 1 end if_kPrime_i_k ; i := i + 1 end while_c_lt_10 end for_k endend.
k = 1: 2 3 5 7 11 13 17 19 23 29k = 2: 4 6 9 10 14 15 21 22 25 26k = 3: 8 12 18 20 27 28 30 42 44 45k = 4: 16 24 36 40 54 56 60 81 84 88k = 5: 32 48 72 80 108 112 120 162 168 176
Works inDyalog APL
f←{↑r⊣⍵∘{r,∘⊂←⍺↑∪{⍵[⍋⍵]},f∘.×⍵}⍣(⍺-1)⊃r←⊂f←pco¨⍳⍵}
5 f 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 4516 24 36 40 54 56 60 81 84 8832 48 72 80 108 112 120 162 168 176
/* ARM assembly Raspberry PI *//* program kprime.s */ /************************************//* Constantes *//************************************/.equ STDOUT, 1 @ Linux output console.equ EXIT, 1 @ Linux syscall.equ WRITE, 4 @ Linux syscall.equ MAXI, 10.equ MAXIK, 5/*********************************//* Initialized data *//*********************************/.datasMessDeb: .ascii "k="sMessValeurDeb: .fill 11, 1, ' ' @ size => 11sMessResult: .ascii " "sMessValeur: .fill 11, 1, ' ' @ size => 11szCarriageReturn: .asciz "\n"/*********************************//* UnInitialized data *//*********************************/.bss /*********************************//* code section *//*********************************/.text.global main main: @ entry of program mov r3,#1 @ k1: @ start loop k mov r0,r3 ldr r1,iAdrsMessValeurDeb bl conversion10 @ call conversion decimal ldr r0,iAdrsMessValeurDeb mov r1,#':' strb r1,[r0,#2] @ write : after k value mov r1,#0 strb r1,[r0,#3] @ final zéro ldr r0,iAdrsMessDeb bl affichageMess @ display message mov r4,#2 @ n mov r5,#0 @ result counter2: @ start loop n mov r0,r4 mov r1,r3 bl kprime @ is kprine ? cmp r0,#0 beq 3f @ no mov r0,r4 ldr r1,iAdrsMessValeur bl conversion10 @ call conversion decimal ldr r0,iAdrsMessValeur mov r1,#0 strb r1,[r0,#4] @ final zéro ldr r0,iAdrsMessResult bl affichageMess @ display message add r5,#1 @ increment counter3: add r4,#1 @ increment n cmp r5,#MAXI @ maxi ? blt 2b @ no -> loop ldr r0,iAdrszCarriageReturn bl affichageMess @ display carriage return add r3,#1 @ increment k cmp r3,#MAXIK @ maxi ? ble 1b @ no -> loop100: @ standard end of the program mov r0, #0 @ return code mov r7, #EXIT @ request to exit program svc #0 @ perform the system call iAdrsMessValeur: .int sMessValeuriAdrszCarriageReturn: .int szCarriageReturniAdrsMessResult: .int sMessResultiAdrsMessValeurDeb: .int sMessValeurDebiAdrsMessDeb: .int sMessDeb/******************************************************************//* compute kprime (n,k) */ /******************************************************************//* r0 contains n *//* r1 contains k */kprime: push {r1-r7,lr} @ save registers mov r5,r0 @ save n mov r7,r1 @ save k mov r4,#0 @ counter product mov r1,#2 @ divisor 1: @ start loop cmp r4,r7 @ counter >= k bge 4f @ yes -> end mul r6,r1,r1 @ compute product cmp r6,r5 @ > n bgt 4f @ yes -> end2: @ start loop division mov r0,r5 @ dividende bl division @ by r1 cmp r3,#0 @ remainder = 0 ? bne 3f @ no mov r5,r2 @ yes -> n = n / r1 add r4,#1 @ increment counter b 2b @ and loop3: add r1,#1 @ increment divisor b 1b @ and loop 4: @ end compute cmp r5,#1 @ n > 1 addgt r4,#1 @ yes increment counter cmp r4,r7 @ counter = k ? movne r0,#0 @ no -> no kprime moveq r0,#1 @ yes -> kprime100: pop {r1-r7,lr} @ restaur registers bx lr @return/******************************************************************//* display text with size calculation */ /******************************************************************//* r0 contains the address of the message */affichageMess: push {r0,r1,r2,r7,lr} @ save registres mov r2,#0 @ counter length 1: @ loop length calculation ldrb r1,[r0,r2] @ read octet start position + index cmp r1,#0 @ if 0 its over addne r2,r2,#1 @ else add 1 in the length bne 1b @ and loop @ so here r2 contains the length of the message mov r1,r0 @ address message in r1 mov r0,#STDOUT @ code to write to the standard output Linux mov r7, #WRITE @ code call system "write" svc #0 @ call systeme pop {r0,r1,r2,r7,lr} @ restaur des 2 registres */ bx lr @ return /******************************************************************//* Converting a register to a decimal unsigned */ /******************************************************************//* r0 contains value and r1 address area *//* r0 return size of result (no zero final in area) *//* area size => 11 bytes */.equ LGZONECAL, 10conversion10: push {r1-r4,lr} @ save registers mov r3,r1 mov r2,#LGZONECAL1: @ start loop bl divisionpar10U @ unsigned r0 <- dividende. quotient ->r0 reste -> r1 add r1,#48 @ digit strb r1,[r3,r2] @ store digit on area cmp r0,#0 @ stop if quotient = 0 subne r2,#1 @ else previous position bne 1b @ and loop @ and move digit from left of area mov r4,#02: ldrb r1,[r3,r2] strb r1,[r3,r4] add r2,#1 add r4,#1 cmp r2,#LGZONECAL ble 2b @ and move spaces in end on area mov r0,r4 @ result length mov r1,#' ' @ space3: strb r1,[r3,r4] @ store space in area add r4,#1 @ next position cmp r4,#LGZONECAL ble 3b @ loop if r4 <= area size 100: pop {r1-r4,lr} @ restaur registres bx lr @return /***************************************************//* division par 10 unsigned *//***************************************************//* r0 dividende *//* r0 quotient *//* r1 remainder */divisionpar10U: push {r2,r3,r4, lr} mov r4,r0 @ save value ldr r3,iMagicNumber @ r3 <- magic_number raspberry 1 2 umull r1, r2, r3, r0 @ r1<- Lower32Bits(r1*r0) r2<- Upper32Bits(r1*r0) mov r0, r2, LSR #3 @ r2 <- r2 >> shift 3 add r2,r0,r0, lsl #2 @ r2 <- r0 * 5 sub r1,r4,r2, lsl #1 @ r1 <- r4 - (r2 * 2) = r4 - (r0 * 10) pop {r2,r3,r4,lr} bx lr @ leave function iMagicNumber: .int 0xCCCCCCCD/***************************************************//* integer division unsigned *//***************************************************/division: /* r0 contains dividend */ /* r1 contains divisor */ /* r2 returns quotient */ /* r3 returns remainder */ push {r4, lr} mov r2, #0 @ init quotient mov r3, #0 @ init remainder mov r4, #32 @ init counter bits b 2f1: @ loop movs r0, r0, LSL #1 @ r0 <- r0 << 1 updating cpsr (sets C if 31st bit of r0 was 1) adc r3, r3, r3 @ r3 <- r3 + r3 + C. This is equivalent to r3 ? (r3 << 1) + C cmp r3, r1 @ compute r3 - r1 and update cpsr subhs r3, r3, r1 @ if r3 >= r1 (C=1) then r3 <- r3 - r1 adc r2, r2, r2 @ r2 <- r2 + r2 + C. This is equivalent to r2 <- (r2 << 1) + C 2: subs r4, r4, #1 @ r4 <- r4 - 1 bpl 1b @ if r4 >= 0 (N=0) then loop pop {r4, lr} bx lrOutput:
k=1 : 2 3 5 7 11 13 17 19 23 29k=2 : 4 6 9 10 14 15 21 22 25 26k=3 : 8 12 18 20 27 28 30 42 44 45k=4 : 16 24 36 40 54 56 60 81 84 88k=5 : 32 48 72 80 108 112 120 162 168 176
almostPrime:function[k,listLen][select.first:listLen1..infinite'n[k=sizefactors.primen]]loop1..5'x->print["k:"x"=>"almostPrimex10]
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]
Translation of the C Version
kprime(n,k){p:=2,f:=0while((f<k)&&(p*p<=n)){while(0==mod(n,p)){n/=pf++}p++}returnf+(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" "ic++}i++}results:=results"`n"k++}MsgBox%results
Output (Msgbox):
k =1: 2 3 5 7 11 13 17 19 23 29k =2: 4 6 9 10 14 15 21 22 25 26k =3: 8 12 18 20 27 28 30 42 44 45k =4: 16 24 36 40 54 56 60 81 84 88k =5: 32 48 72 80 108 112 120 162 168 176
# syntax: GAWK -f ALMOST_PRIME.AWKBEGIN{for(k=1;k<=5;k++){printf("%d:",k)c=0i=1while(c<10){if(kprime(++i,k)){printf(" %d",i)c++}}printf("\n")}exit(0)}functionkprime(n,k,f,p){for(p=2;f<k&&p*p<=n;p++){while(n%p==0){n/=pf++}}return(f+(n>1)==k)}
Output:
1: 2 3 5 7 11 13 17 19 23 292: 4 6 9 10 14 15 21 22 25 263: 8 12 18 20 27 28 30 42 44 454: 16 24 36 40 54 56 60 81 84 885: 32 48 72 80 108 112 120 162 168 176
importballerina/io;functionkPrime(intm,intk)returnsboolean{intn=m;// make mutableintnf=0;foreachintiin2...n{while(n%i)==0{ifnf==k{returnfalse;}nf+=1;n/=i;}}returnnf==k;}functiongen(intk,intm)returnsint[]{int[]r=[];r.setLength(m);intn=2;foreachintiin0..<r.length(){while!kPrime(n,k){n+=1;}r[i]=n;n+=1;}returnr;}publicfunctionmain(){foreachintkin1...5{io:println(k," ",gen(k,10));}}
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]
10DEFINTA-Z20FORK=1TO530PRINTUSING"K = #:";K;40I=2:C=050F=0:P=2:N=I60IFF>=KORP*P>NTHEN10070IFNMODP=0THENN=N/P:F=F+1:GOTO7080P=P+190GOTO60100IFN>1THENF=F+1110IFF=KTHENC=C+1:PRINTUSING" ###";I;120I=I+1130IFC<10THEN50140PRINT150NEXTK
K = 1: 2 3 5 7 11 13 17 19 23 29K = 2: 4 6 9 10 14 15 21 22 25 26K = 3: 8 12 18 20 27 28 30 42 44 45K = 4: 16 24 36 40 54 56 60 81 84 88K = 5: 32 48 72 80 108 112 120 162 168 176
ASIC has both FOR and WHILE loops, but it had better not go out from the loop. So, in the subroutine CHECKKPRIME they are simulated by the constructs with GOTO statements.
REM Almost primeFORK=1TO5S$=STR$(K)S$=LTRIM$(S$)S$="k = "+S$S$=S$+":"PRINTS$;I=2C=0WHILEC<10AN=IGOSUBCHECKKPRIME:IFISKPRIME<>0THENPRINTI;C=C+1ENDIFI=I+1WENDPRINTNEXTKENDCHECKKPRIME:REM Check if N (AN) is a K prime (result: ISKPRIME)F=0J=2LOOPFOR:ANMODJ=ANMODJLOOPWHILE:IFANMODJ<>0THENAFTERWHILE:IFF=KTHENFEQK:F=F+1AN=AN/JANMODJ=ANMODJGOTOLOOPWHILE:AFTERWHILE:J=J+1IFJ<=ANTHENLOOPFOR:IFF=KTHENISKPRIME=-1ELSEISKPRIME=0ENDIFRETURNFEQK:ISKPRIME=0RETURN
k = 1: 2 3 5 7 11 13 17 19 23 29k = 2: 4 6 9 10 14 15 21 22 25 26k = 3: 8 12 18 20 27 28 30 42 44 45k = 4: 16 24 36 40 54 56 60 81 84 88k = 5: 32 48 72 80 108 112 120 162 168 176
functionkPrime(n,k)f=0fori=2tonwhilenmodi=0iff=kthenreturnFalsef+=1n/=iendwhilenextireturnf=kendfunctionfork=1to5print"k = ";k;" :";i=2c=0whilec<10ifkPrime(i,k)thenprintrjust(string(i),4);c+=1endifi+=1endwhileprintnextkend
10'Almost prime20FORk=1TO530PRINT"k = ";k;":";40LETi=250LETc=060WHILEc<1070LETan=i:GOSUB15080IFiskprime<>0THENPRINTUSING" ###";i;:LETc=c+190LETi=i+1100WEND110PRINT120NEXTk130END140' Check if n (AN) is a k (K) prime150LETf=0160FORj=2TOan170WHILEanMODj=0180IFf=kTHENLETiskprime=0:RETURN190LETf=f+1200LETan=INT(an/j)210WEND220NEXTj230LETiskprime=(f=k)240RETURN
fork=1to5print"k = ",k,": ",lete=2letc=0doifc<10thenletn=egosubkprimeifrthenprinttab,e,letc=c+1endiflete=e+1endifloopc<10printnextkendsubkprimeletf=0fori=2tondoifnmodi=0theniff=kthenletr=0returnendifletf=f+1letn=n/iwaitendifloopnmodi=0nextiletr=f=kreturn
k = 1: 2357111317192329k = 2: 46910141521222526k = 3: 8121820272830424445k = 4: 16243640545660818488k = 5: 32487280108112120162168176
' FB 1.05.0 Win64FunctionkPrime(nAsInteger,kAsInteger)AsBooleanDimfAsInteger=0ForiAsInteger=2TonWhilenModi=0Iff=kThenReturnfalsef+=1n\=iWendNextReturnf=kEndFunctionDimAsIntegeri,c,kFork=1To5Print"k = ";k;" : ";i=2c=0Whilec<10IfkPrime(i,k)ThenPrintUsing"### ";i;c+=1EndIfi+=1WendPrintNextPrintPrint"Press any key to quit"Sleep
k = 1 : 2 3 5 7 11 13 17 19 23 29k = 2 : 4 6 9 10 14 15 21 22 25 26k = 3 : 8 12 18 20 27 28 30 42 44 45k = 4 : 16 24 36 40 54 56 60 81 84 88k = 5 : 32 48 72 80 108 112 120 162 168 176
PublicSubMain()DimiAsInteger,cAsInteger,kAsIntegerFork=1To5Print"k = ";k;" : ";i=2c=0Whilec<10IfkPrime(i,k)ThenPrintFormat$(Str$(i),"### ");c+=1EndIfi+=1WendPrintNextEndFunctionkPrime(nAsInteger,kAsInteger)AsBooleanDimfAsInteger=0ForiAsInteger=2TonWhilenModi=0Iff=kThenReturnFalsef+=1n\=iWendNextReturnf=kEndFunction
Same as FreeBASIC entry.
10'Almost prime20FORK%=1TO530PRINT"k = ";K%;":";40LETI%=250LETC%=060WHILEC%<1070LETAN%=I%:GOSUB100080IFISKPRIME<>0THENPRINTUSING" ###";I%;:LETC%=C%+190LETI%=I%+1100WEND110PRINT120NEXTK%130END995' Check if n (AN%) is a k (K%) prime1000LETF%=01010FORJ%=2TOAN%1020WHILEAN%MODJ%=01030IFF%=K%THENLETISKPRIME=0:RETURN1040LETF%=F%+11050LETAN%=AN%\J%1060WEND1070NEXTJ%1080LETISKPRIME=(F%=K%)1090RETURN
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
' Almost primefor k = 1 to 5 print "k = "; k; ":"; i = 2 c = 0 while c < 10 if kPrime(i, k) then print " "; using("###", i); c = c + 1 end if i = i + 1 wend printnext kendfunction kPrime(n, k) f = 0 for i = 2 to n while n mod i = 0 if f = k then kPrime = 0: exit function f = f + 1 n = int(n / i) wend next i kPrime = abs(f = k)end functionk = 1: 2 3 5 7 11 13 17 19 23 29k = 2: 4 6 9 10 14 15 21 22 25 26k = 3: 8 12 18 20 27 28 30 42 44 45k = 4: 16 24 36 40 54 56 60 81 84 88k = 5: 32 48 72 80 108 112 120 162 168 176
10REM Almost prime20FORK=1TO530PRINT"k =";STR$(K);":";40I=250C=060IFC>=10THEN11070AN=I:GOSUB100080IFISKPRIME=0THEN9082REM Print I in 4 fields84S$=STR$(I)86PRINTSPC(4-LEN(S$));S$;88C=C+190I=I+1100GOTO60110PRINT120NEXTK130END995REM Check if N (AN) is a K prime1000F=01010FORJ=2TOAN1020IFINT(AN/J)*J<>ANTHEN10701030IFF=KTHENISKPRIME=0:RETURN1040F=F+11050AN=INT(AN/J)1060GOTO10201070NEXTJ1080ISKPRIME=(F=K)1090RETURN
k = 1: 2 3 5 7 11 13 17 19 23 29k = 2: 4 6 9 10 14 15 21 22 25 26k = 3: 8 12 18 20 27 28 30 42 44 45k = 4: 16 24 36 40 54 56 60 81 84 88k = 5: 32 48 72 80 108 112 120 162 168 176
EnableExplicitProcedure.bkprime(n.i,k.i)Definep.i=2,f.i=0Whilef<kAndp*p<=nWhilen%p=0n/pf+1Wendp+1WendProcedureReturnBool(f+Bool(n>1)=k)EndProcedure;___main____IfNotOpenConsole("Almost prime")End-1EndIfDefinei.i,c.i,k.iFork=1To5Print("k = "+Str(k)+":")i=2c=0Whilec<10Ifkprime(i,k)Print(RSet(Str(i),4))c+1EndIfi+1WendPrintN("")NextInput()
k = 1: 2 3 5 7 11 13 17 19 23 29k = 2: 4 6 9 10 14 15 21 22 25 26k = 3: 8 12 18 20 27 28 30 42 44 45k = 4: 16 24 36 40 54 56 60 81 84 88k = 5: 32 48 72 80 108 112 120 162 168 176
fork=1to5print"k = ";k;" :";i=2c=0whilec<10ifkPrime(i,k)thenprint" ";using("###",i);c=c+1endifi=i+1wendprintnextkendfunctionkPrime(n,k)f=0fori=2tonwhilenmodi=0iff=kthenkPrime=0f=f+1n=int(n/i)wendnextikPrime=abs(f=k)endfunction
REM Almost prime LET K=110 IF K>5 THEN END PRINT "k = ",K,":" LET I=2 LET C=020 IF C>=10 THEN GOTO 40 LET N=I GOSUB 500 IF P=0 THEN GOTO 30 PRINT I LET C=C+130 LET I=I+1 GOTO 2040 LET K=K+1 GOTO 10 REM Check if N is a K prime (result: P)500 LET F=0 LET J=2510 IF (N/J)*J<>N THEN GOTO 520 IF F=K THEN GOTO 530 LET F=F+1 LET N=N/J GOTO 510520 LET J=J+1 IF J<=N THEN GOTO 510 LET P=0 IF F=K THEN LET P=-1 RETURN530 LET P=0 RETURN
k = 1:2357111317192329k = 2:46910141521222526k = 3:8121820272830424445k = 4:16243640545660818488k = 5:32487280108112120162168176
FUNCTIONiskprime(n,k)!Checkifn(AN)isak(K)primeLETf=0FORj=2TOanDOWHILEREMAINDER(an,j)=0IFf=kTHENLETiskprime=0LETf=f+1LETan=INT(an/j)LOOPNEXTjIF(f=k)THENLETiskprime=1ENDFUNCTION!ALMOSTprimeFORk=1TO5PRINT"k = ";k;":";LETi=2LETc=0DOWHILEc<10LETan=iIFiskprime(i,k)<>0THENPRINTUSING" ###":i;LETc=c+1ENDIFLETi=i+1LOOPPRINTNEXTkEND
Local(3)For c@ = 1 To 5 Print "k = ";c@;": "; b@=0 For a@ = 2 Step 1 While b@ < 10 If FUNC(_kprime (a@,c@)) Then b@ = b@ + 1 Print " ";a@; EndIf Next PrintNextEnd_kprime Param(2) Local(2) d@ = 0 For c@ = 2 Step 1 While (d@ < b@) * ((c@ * c@) < (a@ + 1)) Do While (a@ % c@) = 0 a@ = a@ / c@ d@ = d@ + 1 Loop NextReturn (b@ = (d@ + (a@ > 1)))
For k = 1 To 5 Print "k = "; k; " : "; i = 2 c = 0 Do While c < 10 If FUNC(_kPrime(i, k)) Then Print Using "__# "; i; : c = c + 1 i = i + 1 Loop PrintNextEnd_kPrime Param (2) Local (2) c@ = 0 For d@ = 2 To a@ Do While (a@ % d@) = 0 If c@ = b@ Then Unloop: Unloop: Return (0) c@ = c@ + 1 a@ = a@ / d@ Loop NextReturn (c@ = b@)
k = 1: 2 3 5 7 11 13 17 19 23 29k = 2: 4 6 9 10 14 15 21 22 25 26k = 3: 8 12 18 20 27 28 30 42 44 45k = 4: 16 24 36 40 54 56 60 81 84 88k = 5: 32 48 72 80 108 112 120 162 168 1760 OK, 0:200
ModuleModule1ClassKPrimePublicKAsIntegerPublicFunctionIsKPrime(numberAsInteger)AsBooleanDimprimes=0Dimp=2Whilep*p<=numberAndAlsoprimes<KWhilenumberModp=0AndAlsoprimes<Knumber=number/pprimes=primes+1EndWhilep=p+1EndWhileIfnumber>1Thenprimes=primes+1EndIfReturnprimes=KEndFunctionPublicFunctionGetFirstN(nAsInteger)AsList(OfInteger)DimresultAsNewList(OfInteger)Dimnumber=2Whileresult.Count<nIfIsKPrime(number)Thenresult.Add(number)EndIfnumber=number+1EndWhileReturnresultEndFunctionEndClassSubMain()ForEachkInEnumerable.Range(1,5)Dimkprime=NewKPrimeWith{.K=k}Console.WriteLine("k = {0}: {1}",k,String.Join(" ",kprime.GetFirstN(10)))NextEndSubEndModule
k = 1: 2 3 5 7 11 13 17 19 23 29k = 2: 4 6 9 10 14 15 21 22 25 26k = 3: 8 12 18 20 27 28 30 42 44 45k = 4: 16 24 36 40 54 56 60 81 84 88k = 5: 32 48 72 80 108 112 120 162 168 176
' Almost primePROGRAM"almostprime"VERSION"0.0002"DECLAREFUNCTIONEntry()INTERNALFUNCTIONKPrime(n%%,k%%)FUNCTIONEntry()FORk@@=1TO5PRINT"k =";k@@;":";i%%=2c%%=0DOWHILEc%%<10IFTKPrime(i%%,k@@)THENPRINTFORMAT$(" ###",i%%);INCc%%ENDIFINCi%%LOOPPRINTNEXTk@@ENDFUNCTIONFUNCTIONKPrime(n%%,k%%)f%%=0FORi%%=2TOn%%DOWHILEn%%MODi%%=0IFf%%=k%%THENRETURN$$FALSEINCf%%n%%=n%%\i%%LOOPNEXTi%%RETURNf%%=k%%ENDFUNCTIONENDPROGRAM
k = 1: 2 3 5 7 11 13 17 19 23 29k = 2: 4 6 9 10 14 15 21 22 25 26k = 3: 8 12 18 20 27 28 30 42 44 45k = 4: 16 24 36 40 54 56 60 81 84 88k = 5: 32 48 72 80 108 112 120 162 168 176
// Returns boolean indicating whether n is k-almost primesub almostPrime(n, k) local divisor, count divisor = 2 while(count < (k + 1) and n <> 1) if not mod(n, divisor) then n = n / divisor count = count + 1 else divisor = divisor + 1 end if wend return count = kend sub// Generates table containing first ten k-almost primes for given ksub kList(k, kTab()) local n, i n = 2^k : i = 1 while(i < 11) if almostPrime(n, k) then kTab(i) = n i = i + 1 end if n = n + 1 wendend sub// Main procedure, displays results from five calls to kList()dim kTab(10)for k = 1 to 5 print "k = ", k, " : "; kList(k, kTab()) for n = 1 to 10 print kTab(n), ", "; next print "..."next
10FORk=1TO520PRINTk;":";30LETc=0:LETi=140IFc=10THENGOTO10050LETi=i+160GOSUB100070IFrTHENPRINT" ";i;:LETc=c+190GOTO40100PRINT110NEXTk120STOP1000REM kprime1010LETp=2:LETn=i:LETf=01020IFf=kOR(p*p)>nTHENGOTO11001030IFn/p=INT(n/p)THENLETn=n/p:LETf=f+1:GOTO10301040LETp=p+1:GOTO10201100LETr=(f+(n>1)=k)1110RETURN
1: 2 3 5 7 11 13 17 19 23 292: 4 6 9 10 14 15 21 22 25 263: 8 12 18 20 27 28 30 42 44 454: 16 24 36 40 54 56 60 81 84 885: 32 48 72 80 108 112 120 162 168 176
get "libhdr"let kprime(n, k) = valof$( let f, p = 0, 2 while f<k & p*p<=n do $( while n rem p = 0 do $( n := n/p f := f+1 $) p := p+1 $) if n > 1 then f := f + 1 resultis f = k$)let start() be$( for k=1 to 5 do $( let i, c = 2, 0 writef("k = %N:", k) while c < 10 do $( if kprime(i, k) then $( writed(i, 4) c := c+1 $) i := i+1 $) wrch('*N') $)$)k = 1: 2 3 5 7 11 13 17 19 23 29k = 2: 4 6 9 10 14 15 21 22 25 26k = 3: 8 12 18 20 27 28 30 42 44 45k = 4: 16 24 36 40 54 56 60 81 84 88k = 5: 32 48 72 80 108 112 120 162 168 176
The extra spaces are to ensure it's readable on buggy interpreters that don't include a space after numeric output.
1>::48*"= k",,,,02p.":",01v|^v0!`\*:g40:<p402p300:+1<K|>2g03g`*#v_1`03g+02g->|F@>/03g1+03p>vpv+1\.:,*48<P#|!\g40%g40:<4>:9`>#v_\1^||^>#!1#`+#50#:^#+1,+5>#5$<|
k = 1 : 2 3 5 7 11 13 17 19 23 29k = 2 : 4 6 9 10 14 15 21 22 25 26k = 3 : 8 12 18 20 27 28 30 42 44 45k = 4 : 16 24 36 40 54 56 60 81 84 88k = 5 : 32 48 72 80 108 112 120 162 168 176
#include<stdio.h>intkprime(intn,intk){intp,f=0;for(p=2;f<k&&p*p<=n;p++)while(0==n%p)n/=p,f++;returnf+(n>1)==k;}intmain(void){inti,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');}return0;}
k = 1: 2 3 5 7 11 13 17 19 23 29k = 2: 4 6 9 10 14 15 21 22 25 26k = 3: 8 12 18 20 27 28 30 42 44 45k = 4: 16 24 36 40 54 56 60 81 84 88k = 5: 32 48 72 80 108 112 120 162 168 176
usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;namespaceAlmostPrime{classProgram{staticvoidMain(string[]args){foreach(intkinEnumerable.Range(1,5)){KPrimekprime=newKPrime(){K=k};Console.WriteLine("k = {0}: {1}",k,string.Join<int>(" ",kprime.GetFirstN(10)));}}}classKPrime{publicintK{get;set;}publicboolIsKPrime(intnumber){intprimes=0;for(intp=2;p*p<=number&&primes<K;++p){while(number%p==0&&primes<K){number/=p;++primes;}}if(number>1){++primes;}returnprimes==K;}publicList<int>GetFirstN(intn){List<int>result=newList<int>();for(intnumber=2;result.Count<n;++number){if(IsKPrime(number)){result.Add(number);}}returnresult;}}}
k = 1: 2 3 5 7 11 13 17 19 23 29k = 2: 4 6 9 10 14 15 21 22 25 26k = 3: 8 12 18 20 27 28 30 42 44 45k = 4: 16 24 36 40 54 56 60 81 84 88k = 5: 32 48 72 80 108 112 120 162 168 176
#include<cstdlib>#include<iostream>#include<sstream>#include<iomanip>#include<list>boolk_prime(unsignedn,unsignedk){unsignedf=0;for(unsignedp=2;f<k&&p*p<=n;p++)while(0==n%p){n/=p;f++;}returnf+(n>1?1:0)==k;}std::list<unsigned>primes(unsignedk,unsignedn){std::list<unsigned>list;for(unsignedi=2;list.size()<n;i++)if(k_prime(i,k))list.push_back(i);returnlist;}intmain(constintargc,constchar*argv[]){usingnamespacestd;for(unsignedk=1;k<=5;k++){ostringstreamos("");constlist<unsigned>l=primes(k,10);for(list<unsigned>::const_iteratori=l.begin();i!=l.end();i++)os<<setw(4)<<*i;cout<<"k = "<<k<<':'<<os.str()<<endl;}returnEXIT_SUCCESS;}
k = 1: 2 3 5 7 11 13 17 19 23 29k = 2: 4 6 9 10 14 15 21 22 25 26k = 3: 8 12 18 20 27 28 30 42 44 45k = 4: 16 24 36 40 54 56 60 81 84 88k = 5: 32 48 72 80 108 112 120 162 168 176
(nsclojure.examples.almostprime(:gen-class))(defndivisors[n]" Finds divisors by looping through integers 2, 3,...i.. up to sqrt (n) [note: rather than compute sqrt(), test with i*i <=n] "(let[div(some#(if(=0(modn%))%nil)(take-while#(<=(*%%)n)(iterate inc2)))](ifdiv; div = nil (if no divisor found else its the divisor)(into[](concat(divisorsdiv)(divisors(/ndiv)))); Concat the two divisors of the two divisors[n]))); Number is prime so only itself as a divisor(defndivisors-k[kn]" Finds n numbers with k divisors. Does this by looping through integers 2, 3, ... filtering (passing) ones with k divisors and taking the first n "(->>(iterate inc2); infinite sequence of numbers starting at 2(mapdivisors); compute divisor of each element of sequence(filter#(=(count%)k)); filter to take only elements with k divisors(taken); take n elements from filtered sequence(map#(apply *%)))); compute number by taking product of divisors(println(for[k(range16)](println"k:"k(divisors-kk10))))
(k = 1: 2 3 5 7 11 13 17 19 23 29k = 2: 4 6 9 10 14 15 21 22 25 26k = 3: 8 12 18 20 27 28 30 42 44 45k = 4: 16 24 36 40 54 56 60 81 84 88k = 5: 32 48 72 80 108 112 120 162 168 176)nil
kprime = proc (n,k: int) returns (bool) f: int := 0 p: int := 2 while f<k & p*p<=n do while n//p=0 do n := n/p f := f+1 end p := p+1 end if n>1 then f:=f+1 end return(f=k)end kprimestart_up = proc () po: stream := stream$primary_output() for k: int in int$from_to(1,5) do i: int := 2 c: int := 0 stream$puts(po, "k = " || int$unparse(k) || ":") while c<10 do if kprime(i,k) then stream$putright(po, int$unparse(i), 4) c := c+1 end i := i+1 end stream$putl(po, "") endend start_up
k = 1: 2 3 5 7 11 13 17 19 23 29k = 2: 4 6 9 10 14 15 21 22 25 26k = 3: 8 12 18 20 27 28 30 42 44 45k = 4: 16 24 36 40 54 56 60 81 84 88k = 5: 32 48 72 80 108 112 120 162 168 176
IDENTIFICATIONDIVISION.PROGRAM-ID.ALMOST-PRIME.DATADIVISION.WORKING-STORAGESECTION.01CONTROL-VARS.03KPIC 9.03IPIC 999.03SEENPIC 99.03NPIC 999.03PPIC 99.03P-SQUAREDPIC 9(4).03FPIC 99.03N-DIV-PPIC 999V999.03FILLERREDEFINESN-DIV-P.05NEXT-NPIC 999.05FILLERPIC 999.88N-DIVS-PVALUEZERO.01OUT-VARS.03K-LNPIC X(70).03K-LN-PTRPIC 99.03LN-HDR.05FILLERPIC X(4)VALUE"K = ".05K-OUTPIC 9.05FILLERPIC XVALUE":".03I-FMT.05FILLERPIC XVALUESPACE.05I-OUTPIC ZZ9.PROCEDUREDIVISION.BEGIN.PERFORMK-ALMOST-PRIMESVARYINGKFROM1BY1UNTILKISGREATERTHAN5.STOPRUN.K-ALMOST-PRIMES.MOVESPACESTOK-LN.MOVE1TOK-LN-PTR.MOVEZEROTOSEEN.MOVEKTOK-OUT.STRINGLN-HDRDELIMITEDBYSIZEINTOK-LNWITHPOINTERK-LN-PTR.PERFORMI-K-ALMOST-PRIMEVARYINGIFROM2BY1UNTILSEENISEQUALTO10.DISPLAYK-LN.I-K-ALMOST-PRIME.MOVEZEROTOF,P-SQUARED.MOVEITON.PERFORMPRIME-FACTORVARYINGPFROM2BY1UNTILFISNOTLESSTHANKORP-SQUAREDISGREATERTHANN.IFNISGREATERTHAN1,ADD1TOF.IFFISEQUALTOK,MOVEITOI-OUT,ADD1TOSEEN,STRINGI-FMTDELIMITEDBYSIZEINTOK-LNWITHPOINTERK-LN-PTR.PRIME-FACTOR.MULTIPLYPBYPGIVINGP-SQUARED.DIVIDENBYPGIVINGN-DIV-P.PERFORMDIVIDE-FACTORUNTILNOTN-DIVS-P.DIVIDE-FACTOR.MOVENEXT-NTON.ADD1TOF.DIVIDENBYPGIVINGN-DIV-P.
K = 1: 2 3 5 7 11 13 17 19 23 29K = 2: 4 6 9 10 14 15 21 22 25 26K = 3: 8 12 18 20 27 28 30 42 44 45K = 4: 16 24 36 40 54 56 60 81 84 88K = 5: 32 48 72 80 108 112 120 162 168 176
(defunstart()(loopforkfrom1to5do(formatt"k = ~a: ~a~%"k(collect-k-almost-primek))))(defuncollect-k-almost-prime(k&optional(d2)(lstnil))(cond((=(lengthlst)10)(reverselst))((=(?-primalityd)k)(collect-k-almost-primek(+d1)(consdlst)))(t(collect-k-almost-primek(+d1)lst))))(defun?-primality(n&optional(d2)(c0))(cond((>d(isqrtn))(+c1))((zerop(remnd))(?-primality(/nd)d(+c1)))(t(?-primalityn(+d1)c))))
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
include "cowgol.coh";sub kprime(n: uint8, k: uint8): (kp: uint8) is var p: uint8 := 2; var f: uint8 := 0; while f < k and p*p <= n loop while 0 == n % p loop n := n / p; f := f + 1; end loop; p := p + 1; end loop; if n > 1 then f := f + 1; end if; if f == k then kp := 1; else kp := 0; end if;end sub;var k: uint8 := 1;while k <= 5 loop print("k = "); print_i8(k); print(":"); var i: uint8 := 2; var c: uint8 := 0; while c < 10 loop if kprime(i,k) != 0 then print(" "); print_i8(i); c := c + 1; end if; i := i + 1; end loop; print_nl(); k := k + 1;end loop;k = 1: 2 3 5 7 11 13 17 19 23 29k = 2: 4 6 9 10 14 15 21 22 25 26k = 3: 8 12 18 20 27 28 30 42 44 45k = 4: 16 24 36 40 54 56 60 81 84 88k = 5: 32 48 72 80 108 112 120 162 168 176
This contains a copy of the functiondecompose from the Prime decomposition task.
importstd.stdio,std.algorithm,std.traits;Unqual!T[]decompose(T)(inTnumber)purenothrowin{assert(number>1);}body{typeof(return)result;Unqual!Tn=number;for(Unqual!Ti=2;n%i==0;n/=i)result~=i;for(Unqual!Ti=3;n>=i*i;i+=2)for(;n%i==0;n/=i)result~=i;if(n!=1)result~=n;returnresult;}voidmain(){enumoutLength=10;// 10 k-th almost primes.foreach(immutablek;1..6){writef("K = %d: ",k);auton=2;// The "current number" to be checked.foreach(immutablei;1..outLength+1){while(n.decompose.length!=k)n++;// Now n is K-th almost prime.write(n," ");n++;}writeln;}}
K = 1: 2 3 5 7 11 13 17 19 23 29K = 2: 4 6 9 10 14 15 21 22 25 26K = 3: 8 12 18 20 27 28 30 42 44 45K = 4: 16 24 36 40 54 56 60 81 84 88K = 5: 32 48 72 80 108 112 120 162 168 176
programAlmostPrime;{$APPTYPE CONSOLE}functionIsKPrime(constn,k:Integer):Boolean;varp,f,v:Integer;beginf:=0;p:=2;v:=n;while(f<k)and(p*p<=n)dobeginwhile(vmodp)=0dobeginv:=vdivp;Inc(f);end;Inc(p);end;ifv>1thenInc(f);Result:=f=k;end;vari,c,k:Integer;beginfork:=1to5dobeginWrite('k = ',k,':');c:=0;i:=2;whilec<10dobeginifIsKPrime(i,k)thenbeginWrite(' ',i);Inc(c);end;Inc(i);end;WriteLn;end;end.
K = 1: 2 3 5 7 11 13 17 19 23 29K = 2: 4 6 9 10 14 15 21 22 25 26K = 3: 8 12 18 20 27 28 30 42 44 45K = 4: 16 24 36 40 54 56 60 81 84 88K = 5: 32 48 72 80 108 112 120 162 168 176
proc nonrec kprime(word n, k) bool: word f, p; f := 0; p := 2; while f < k and p*p <= n do while n%p = 0 do n := n/p; f := f+1 od; p := p+1 od; if n>1 then f+1 = k else f = k ficorpproc nonrec main() void: byte k, i, c; for k from 1 upto 5 do write("k = ", k:1, ":"); i := 2; c := 0; while c < 10 do if kprime(i,k) then write(i:4); c := c+1 fi; i := i+1 od; writeln() odcorpk = 1: 2 3 5 7 11 13 17 19 23 29k = 2: 4 6 9 10 14 15 21 22 25 26k = 3: 8 12 18 20 27 28 30 42 44 45k = 4: 16 24 36 40 54 56 60 81 84 88k = 5: 32 48 72 80 108 112 120 162 168 176
func kprime n k . i = 2 while i <= n while n mod i = 0 if f = k : return 0 f += 1 n /= i . i += 1 . if f = k : return 1 return 0.for k = 1 to 5 write "k=" & k & " : " i = 2 cnt = 0 while cnt < 10 if kprime i k = 1 write i & " " cnt += 1 . i += 1 . print "".
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
Small numbers : filter the sequence [ 2 .. n]
(define(almost-prime?pk)(=k(length(prime-factorsp))))(define(almost-primesknmax)(take(filter(rcurryalmost-prime?k)[2..])nmax))(define(task(kmax6)(nmax10))(for((k[1..kmax]))(write'k=k'|)(for-eachwrite(almost-primesknmax))(writeln)))
(task)k=1|2357111317192329k=2|46910141521222526k=3|8121820272830424445k=4|16243640545660818488k=5|32487280108112120162168176
Large numbers : generate - combinations with repetitions - k-almost-primes up to pmax.
(lib'match)(define-syntax-rule(:vi)(vector-refvi))(reader-infix':);; abbrev (vector-ref v i) === [v : i](lib'bigint)(definecprimes(list->vector(primes10000)));; generates next k-almost-prime < pmax;; c = vector of k primes indices c[i] <= c[j];; p = vector of intermediate products prime[c[0]]*prime[c[1]]*..;; p[k-1] is the generated k-almost-prime;; increment one c[i] at each step(define(almost-nextpmaxkcp)(definealmost-prime#f)(definecp0)(for((i(in-range(1-k)-1-1)));; look backwards for c[i] to increment(vector-set!ci(1+[c:i]));; increment c[i](set!cp[cprimes:[c:i]])(vector-set!pi(if(>i0)(*[p:(1-i)]cp)cp));; update partial product(when(<[p:i)pmax)(set!almost-prime(and;; set followers to c[i] value(for((j(in-range(1+i)k)))(vector-set!cj[c:i])(vector-set!pj(*[p:(1-j)]cp))#:break(>=[p:j]pmax)=>#f)[p:(1-k)]);; // and);; set!);; when#:breakalmost-prime);; // for ialmost-prime);; not sorted list of k-almost-primes < pmax(define(almost-primesknmax)(definebase(expt2k));; first one is 2^k(definepmax(*basenmax))(definec(make-vectork#0))(definep(build-vectork(lambda(i)(expt#2(1+i)))))(consbase(for/list((almost-prime(in-produceralmost-nextpmaxkcp)))almost-prime)))
;; we want 500-almost-primes from the 10000-th.(take(drop(list-sort<(almost-primes50010000))10000)10)(7241149198492252834202927258094752774597239286103014697435725917649659974371690699721153852986440733637405206125678822081264723636566725108094369093648384etc...;; The first one is 2^497 * 3 * 17 * 347 , same result as Haskell.
defmoduleFactorsdodeffactors(n),do:factors(n,2,[])defpfactors(1,_,acc),do:accdefpfactors(n,k,acc)whenrem(n,k)==0,do:factors(div(n,k),k,[k|acc])defpfactors(n,k,acc),do:factors(n,k+1,acc)defkfactors(n,k),do:kfactors(n,k,1,1,[])defpkfactors(_tn,tk,_n,k,_acc)whenk==tk+1,do:IO.puts"done! "defpkfactors(tn,tk,_n,k,acc)whenlength(acc)==tndoIO.puts"K:#{k}#{inspectacc}"kfactors(tn,tk,2,k+1,[])enddefpkfactors(tn,tk,n,k,acc)docaselength(factors(n))do^k->kfactors(tn,tk,n+1,k,acc++[n])_->kfactors(tn,tk,n+1,k,acc)endendendFactors.kfactors(10,5)
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]done!
Using the factors function fromPrime_decomposition#Erlang.
-module(factors).-export([factors/1,kfactors/0,kfactors/2]).factors(N)->factors(N,2,[]).factors(1,_,Acc)->Acc;factors(N,K,Acc)whenNremK==0->factors(NdivK,K,[K|Acc]);factors(N,K,Acc)->factors(N,K+1,Acc).kfactors()->kfactors(10,5,1,1,[]).kfactors(N,K)->kfactors(N,K,1,1,[]).kfactors(_Tn,Tk,_N,K,_Acc)whenK==Tk+1->io:fwrite("Done! ");kfactors(Tn,Tk,N,K,Acc)whenlength(Acc)==Tn->io:format("K:~w~w~n",[K,Acc]),kfactors(Tn,Tk,2,K+1,[]);kfactors(Tn,Tk,N,K,Acc)->caselength(factors(N))ofK->kfactors(Tn,Tk,N+1,K,Acc++[N]);_->kfactors(Tn,Tk,N+1,K,Acc)end.
9> factors:kfactors(10,5). 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] Done! ok10> factors:kfactors(15,10).K: 1 [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47] K: 2 [4,6,9,10,14,15,21,22,25,26,33,34,35,38,39] K: 3 [8,12,18,20,27,28,30,42,44,45,50,52,63,66,68] K: 4 [16,24,36,40,54,56,60,81,84,88,90,100,104,126,132] K: 5 [32,48,72,80,108,112,120,162,168,176,180,200,208,243,252] K: 6 [64,96,144,160,216,224,240,324,336,352,360,400,416,486,504] K: 7 [128,192,288,320,432,448,480,648,672,704,720,800,832,972,1008] K: 8 [256,384,576,640,864,896,960,1296,1344,1408,1440,1600,1664,1944,2016] K: 9 [512,768,1152,1280,1728,1792,1920,2592,2688,2816,2880,3200,3328,3888,4032] K: 10 [1024,1536,2304,2560,3456,3584,3840,5184,5376,5632,5760,6400,6656,7776,8064] Done! ok
PROGRAM ALMOST_PRIME!! for rosettacode.org!!$INTEGERPROCEDURE 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 PROCEDUREBEGIN 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 FOREND PROGRAMK = 1: 2 3 5 7 11 13 17 19 23 29K = 2: 4 6 9 10 14 15 21 22 25 26K = 3: 8 12 18 20 27 28 30 42 44 45K = 4: 16 24 36 40 54 56 60 81 84 88K = 5: 32 48 72 80 108 112 120 162 168 176
letrecgenFactor(f,n)=iff>nthenNoneelifn%f=0thenSome(f,(f,n/f))elsegenFactor(f+1,n)letfactorsOf(num)=Seq.unfold(fun(f,n)->genFactor(f,n))(2,num)letkFactorsk=Seq.unfold(funn->letrecloopm=ifSeq.length(factorsOfm)=kthenmelseloop(m+1)letnext=loopnSome(next,next+1))2[1..5]|>List.iter(funk->printfn"%A"(Seq.take10(kFactorsk)|>Seq.toList))
[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]
USING:formattingfrykernellistslists.lazylocalsmath.combinatoricsmath.primes.factorsmath.rangessequences;IN:rosetta-code.almost-prime:k-almost-prime?(nk--?)'[factors_<combinations>[product]map][[=]curry]biany?;::first10(k--seq)10 0lfrom[kk-almost-prime?]lfilterltakelist>array;5[1,b][dupfirst10"K = %d: %[%3d, %]\n"printf]each
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 }(do;;; show some k-almost-primes - translation of C via Algol W(fnk-almost-prime?[nvk](var(pfn)(values30nv))(while(and(<=fk)(=(%n2)0))(set(nf)(values(math.floor(/n2))(+f1))))(while(and(<=fk)(<=(*pp)n))(while(=(%np)0)(set(nf)(values(math.floor(/np))(+f1))))(setp(+p2)))(when(>n1)(setf(+f1)))(=fk))(do;;; task(for[k15](var(cikNumbers)(values02{}))(while(<c10)(when(k-almost-prime?ik)(table.insertkNumbers(string.format"%3d"i))(setc(+c1)))(seti(+i1)))(print(.."k = "k": "(table.concatkNumbers" "))))))
k = 1: 2 3 5 7 11 13 17 19 23 29k = 2: 4 6 9 10 14 15 21 22 25 26k = 3: 8 12 18 20 27 28 30 42 44 45k = 4: 16 24 36 40 54 56 60 81 84 88k = 5: 32 48 72 80 108 112 120 162 168 176
01.10 F K=1,5;D 301.20 Q02.10 S N=I;S P=1;S G=002.20 S P=P+102.30 I (K-G)2.7,2.7;I (N-P*P)2.702.40 S Z=FITR(N/P)02.50 I (Z*P-N)2.202.60 S N=Z;S G=G+1;G 2.402.70 I (1-N)2.8;R02.80 S G=G+103.10 T "K",%1,K,":"03.20 S I=2;S C=003.30 D 2;I (G-K)3.6,3.4,3.603.40 T " ",%3,I03.50 S C=C+103.60 S I=I+103.70 I (C-10)3.303.80 T !
K= 1: = 2 = 3 = 5 = 7 = 11 = 13 = 17 = 19 = 23 = 29K= 2: = 4 = 6 = 9 = 10 = 14 = 15 = 21 = 22 = 25 = 26K= 3: = 8 = 12 = 18 = 20 = 27 = 28 = 30 = 42 = 44 = 45K= 4: = 16 = 24 = 36 = 40 = 54 = 56 = 60 = 81 = 84 = 88K= 5: = 32 = 48 = 72 = 80 = 108 = 112 = 120 = 162 = 168 = 176
:multiplicity( n1 n2 -- n1 n2 n3 )0>rbegin2dupmod0=whiler>1+>rtuck/swaprepeatr>;:k-prime?( n k -- ? )>r0>r2begin2dupdup*>=if2r@>elsefalsethenwhilemultiplicityr>+>r1+repeatdrop1>if1else0thenr>+r>=;:next-k-prime( n k -- n )beginswap1+swap2dupk-prime?untildrop;:main61do."k ="i1.r.":"1100dojnext-k-primedup3.rspaceloopdropcrloop;mainbye
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
programalmost_primeuseiso_fortran_env,only:output_unitimplicit noneinteger::i,c,kdok=1,5write(output_unit,'(A3,x,I0,x,A1,x)',advance="no")"k =",k,":"i=2c=0do if(c>=10)exit if(kprime(i,k))then write(output_unit,'(I0,x)',advance="no")ic=c+1end ifi=i+1end do write(output_unit,*)end docontains pure functionkprime(n,k)integer,intent(in)::n,klogical::kprimeinteger::p,f,ikprime=.false.f=0i=ndop=2,ndo if(modulo(i,p)/=0)exit if(f==k)returnf=f+1i=i/pend do end dokprime=f==kend functionkprimeend programalmost_prime
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
for k = 1 to 5{ n=2 count = 0 print["k=$k:"] do { if length[factorFlat[n]] == k { print[" $n"] count = count + 1 } n = n + 1 } while count < 10 println[]}Output:
k=1: 2 3 5 7 11 13 17 19 23 29k=2: 4 6 9 10 14 15 21 22 25 26k=3: 8 12 18 20 27 28 30 42 44 45k=4: 16 24 36 40 54 56 60 81 84 88k=5: 32 48 72 80 108 112 120 162 168 176
letkprime(n:i32,k:i32):bool=let(p,f)=(2,0)let(n,_,f)=loop(n,p,f)whilef<k&&p*p<=ndolet(n,f)=loop(n,f)while0==n%pdo(n/p,f+1)in(n,p+1,f)inf+(ifn>1then1else0)==kletmain(m:i32):[][]i32=letfk=letps=replicate100let(_,_,ps)=loop(i,c,ps)=(2,0,ps)whilec<10doifkprime(i,k)thenunsafeletps[c]=iin(i+1,c+1,ps)else(i+1,c,ps)inpsinmapf(1...m)
This fn uses FB's MDA arrays, one for each k, to store the lists.
local fn almostPrimes uint8 i = 1, primes( 50 ) = {2,3,5,7,11,13,17,19,23,29,31,¬ 37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,¬ 131,137,139,149,151,157,163,167,173,179,109,113,127} while 10 > mda_count 5 // Quit when k=5 list is filled int k = 0, x = 0, n = i while n > 1 if (n % primes(x)) then x++ else k++ : n /= primes(x) wend mda_add k = i i++ wendend fnwindow 1, @"Almost primes"fn almostPrimesprintf @" Almost primes from 2 to %d with k prime factors:", mda_integer 5 (9)for int k = 1 to 5 printf @"\n k=%d:\b",k for int i = 0 to 9 printf @"%5d\b", mda_integer k ( i ) next printf @" + %2d more.", (mda_count k) - 10nextHandleEventsAlmost primes from 2 to 176 with k prime factors: k=1: 2 3 5 7 11 13 17 19 23 29 + 30 more. k=2: 4 6 9 10 14 15 21 22 25 26 + 46 more. k=3: 8 12 18 20 27 28 30 42 44 45 + 33 more. k=4: 16 24 36 40 54 56 60 81 84 88 + 11 more. k=5: 32 48 72 80 108 112 120 162 168 176 + 0 more.
packagemainimport"fmt"funckPrime(n,kint)bool{nf:=0fori:=2;i<=n;i++{forn%i==0{ifnf==k{returnfalse}nf++n/=i}}returnnf==k}funcgen(k,nint)[]int{r:=make([]int,n)n=2fori:=ranger{for!kPrime(n,k){n++}r[i]=nn++}returnr}funcmain(){fork:=1;k<=5;k++{fmt.Println(k,gen(k,10))}}
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]
publicclassalmostprime{publicstaticbooleankprime(intn,intk){inti,div=0;for(i=2;(i*i<=n)&&(div<k);i++){while(n%i==0){n=n/i;div++;}}returndiv+((n>1)?1:0)==k;}publicstaticvoidmain(String[]args){inti,l,k;for(k=1;k<=5;k++){println("k = "+k+":");l=0;for(i=2;l<10;i++){if(kprime(i,k)){print(i+" ");l++;}}println();}}}
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
isPrime::Integrala=>a->BoolisPrimen=not$any((0==).(modn))[2..(truncate$sqrt$fromIntegraln)]primes::[Integer]primes=filterisPrime[2..]isKPrime::(Numa,Eqa)=>a->Integer->BoolisKPrime1n=isPrimenisKPrimekn=any(isKPrime(k-1))sprimeswheresprimes=mapfst$filter((0==).snd)$map(divModn)$takeWhile(<n)primeskPrimes::(Numa,Eqa)=>a->[Integer]kPrimesk=filter(isKPrimek)[2..]main::IO()main=flipmapM_[1..5]$\k->putStrLn$"k = "++showk++": "++(unwords$mapshow(take10$kPrimesk))
k = 1: 2 3 5 7 11 13 17 19 23 29k = 2: 4 6 9 10 14 15 21 22 25 26k = 3: 8 12 18 20 27 28 30 42 44 45k = 4: 16 24 36 40 54 56 60 81 84 88k = 5: 32 48 72 80 108 112 120 162 168 176
Largerks require more complicated methods:
primes=2:3:[n|n<-[5,7..],foldr(\pr->p*p>n||remnp>0&&r)True(drop1primes)]mergeaa@(a:as)bb@(b:bs)|a<b=a:mergeasbb|otherwise=b:mergeaabs-- n-th item is all k-primes not divisible by any of the first n primesnotdivsk=fprimes$kprimes(k-1)wheref(p:ps)s=map(p*)s:fps(filter((/=0).(`mod`p))s)kprimesk|k==1=primes|otherwise=f(headndk)(tailndk)(tail$map(^k)primes)wherendk=notdivsk-- tt is the thresholds for merging in next sequence-- it is equal to "map head seqs", but don't do thatfaa@(a:as)seqstt@(t:ts)|a<t=a:fasseqstt|otherwise=f(mergeaa$headseqs)(tailseqs)tsmain=do-- next line is for task requirement:mapM_(\x->print(x,take10$kprimesx))[1..5]putStrLn"\n10000th to 10100th 500-amost primes:"mapM_print$take100$drop10000$kprimes500
(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...>
Works in both languages.
link"factors"proceduremain()everywrites(k:=1to5,": ")doeverywrites(right(genKap(k),5)\10|"\n")endproceduregenKap(k)suspend(k=*factors(n:=seq()),n)end
Output:
->ap1: 2 3 5 7 11 13 17 19 23 292: 4 6 9 10 14 15 21 22 25 263: 8 12 18 20 27 28 30 42 44 454: 16 24 36 40 54 56 60 81 84 885: 32 48 72 80 108 112 120 162 168 176->
(function prime-sieve search siever sieved (return-when (empty? siever) (.. vec sieved search)) (let [p ps] ((juxt 0 (skip 1)) siever)) (recur (remove #(div? % p) search) (remove #(div? % p) ps) (append p sieved)))(function primes n (prime-sieve (range 2 (inc n)) (range 2 (ceil (sqrt n))) []))(function decompose n ps factors (return-when (= n 1) factors) (let div (find (div? n) ps)) (recur (/ n div) ps (append div factors)))(function almost-prime up-to n k (return-when (zero? up-to) []) (let ps (primes n)) (if (= k (len (decompose n ps []))) (prepend n (almost-prime (dec up-to) (inc n) k)) (almost-prime up-to (inc n) k)))(function row n (-> n @(almost-prime 10 1) (join " ") @(str n (match n 1 "st" 2 "nd" 3 "rd" "th") " almost-primes: " )))(join "\n" (map row (range 1 6)))
1st almost-primes: 2 3 5 7 11 13 17 19 23 292nd almost-primes: 4 6 9 10 14 15 21 22 25 263rd almost-primes: 8 12 18 20 27 28 30 42 44 454th almost-primes: 16 24 36 40 54 56 60 81 84 885th almost-primes: 32 48 72 80 108 112 120 162 168 176
(10{.[:~.[:/:~[:,*/~)^:(i.5)~p:i.1023571113171923294691014152122252681218202728304244451624364054566081848832487280108112120162168176
Explanation:
The results of the odd steps in this procedure are the desired result.
publicclassAlmostPrime{publicstaticvoidmain(String[]args){for(intk=1;k<=5;k++){System.out.print("k = "+k+":");for(inti=2,c=0;c<10;i++){if(kprime(i,k)){System.out.print(" "+i);c++;}}System.out.println("");}}publicstaticbooleankprime(intn,intk){intf=0;for(intp=2;f<k&&p*p<=n;p++){while(n%p==0){n/=p;f++;}}returnf+((n>1)?1:0)==k;}}
k = 1: 2 3 5 7 11 13 17 19 23 29k = 2: 4 6 9 10 14 15 21 22 25 26k = 3: 8 12 18 20 27 28 30 42 44 45k = 4: 16 24 36 40 54 56 60 81 84 88k = 5: 32 48 72 80 108 112 120 162 168 176
functionalmostPrime(n,k){vardivisor=2,count=0while(count<k+1&&n!=1){if(n%divisor==0){n=n/divisorcount=count+1}else{divisor++}}returncount==k}for(vark=1;k<=5;k++){document.write("<br>k=",k,": ")varcount=0,n=0while(count<=10){n++if(almostPrime(n,k)){document.write(n," ")count++}}}
k=1: 2 3 5 7 11 13 17 19 23 29 31k=2: 4 6 9 10 14 15 21 22 25 26 33k=3: 8 12 18 20 27 28 30 42 44 45 50k=4: 16 24 36 40 54 56 60 81 84 88 90k=5: 32 48 72 80 108 112 120 162 168 176 180
Infrastructure:
# 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 orderdef 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;
isalmostprime
def isalmostprime(k): (prime_factors_with_multiplicities | length) == k;# Emit a stream of the first N almost-k primesdef 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;
The task:
range(1;6) as $k | "k=\($k): \([almostprimes(10;$k)])"
$jq-c-r-n-fAlmost_prime.jqk=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]
usingPrimesisalmostprime(n::Integer,k::Integer)=sum(values(factor(n)))==kfunctionalmostprimes(N::Integer,k::Integer)# return first N almost-k primesP=Vector{typeof(k)}(undef,N)i=0;n=2whilei<Nifisalmostprime(n,k)P[i+=1]=nendn+=1endreturnPendforkin1:5println("$k-Almost-primes: ",join(almostprimes(10,k),", "),"...")end
1-Almost-primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29...2-Almost-primes: 4, 6, 9, 10, 14, 15, 21, 22, 25, 26...3-Almost-primes: 8, 12, 18, 20, 27, 28, 30, 42, 44, 45...4-Almost-primes: 16, 24, 36, 40, 54, 56, 60, 81, 84, 88...5-Almost-primes: 32, 48, 72, 80, 108, 112, 120, 162, 168, 176...
funInt.k_prime(x:Int):Boolean{varn=xvarf=0varp=2while(f<this&&p*p<=n){while(0==n%p){n/=p;f++}p++}returnf+(if(n>1)1else0)==this}funInt.primes(n:Int):List<Int>{vari=2varlist=mutableListOf<Int>()while(list.size<n){if(k_prime(i))list.add(i)i++}returnlist}funmain(args:Array<String>){for(kin1..5)println("k = $k: "+k.primes(10))}
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]
-- Returns boolean indicating whether n is k-almost primefunctionalmostPrime(n,k)localdivisor,count=2,0whilecount<k+1andn~=1doifn%divisor==0thenn=n/divisorcount=count+1elsedivisor=divisor+1endendreturncount==kend-- Generates table containing first ten k-almost primes for given kfunctionkList(k)localn,kTab=2^k,{}while#kTab<10doifalmostPrime(n,k)thentable.insert(kTab,n)endn=n+1endreturnkTabend-- Main procedure, displays results from five calls to kList()fork=1,5doio.write("k="..k..": ")for_,vinpairs(kList(k))doio.write(v..", ")endprint("...")end
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, ...
AlmostPrimes:=proc(k,numvalues::posint:=10)localaprimes,i,intfactors;aprimes:=Array([]);i:=0;doi:=i+1;intfactors:=ifactors(i)[2];intfactors:=[seq(seq(intfactors[i][1],j=1..intfactors[i][2]),i=1..numelems(intfactors))];ifnumelems(intfactors)=kthenArrayTools:-Append(aprimes,i);endif;untilnumelems(aprimes)=10:aprimes;endproc:<seq(AlmostPrimes(i),i=1..5)>;
[[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]]
NORMAL MODE IS INTEGER INTERNAL FUNCTION(NN,KK) ENTRY TO KPRIME. F = 0 N = NN THROUGH SCAN, FOR P=2, 1, F.GE.KK .OR. P*P.G.NDIV WHENEVER N.E.N/P*P N = N/P F = F+1 TRANSFER TO DIV END OF CONDITIONALSCAN CONTINUE WHENEVER N.G.1, F = F+1 FUNCTION RETURN F.E.KK END OF FUNCTION VECTOR VALUES KFMT = $5(S1,2HK=,I1,S1)*$ VECTOR VALUES PFMT = $5(I4,S1)*$ PRINT FORMAT KFMT, 1, 2, 3, 4, 5 DIMENSION KPR(50) THROUGH FNDKPR, FOR K=1, 1, K.G.5 C=0 THROUGH FNDKPR, FOR I=2, 1, C.GE.10 WHENEVER KPRIME.(I,K) KPR(C*5+K) = I C = C+1 END OF CONDITIONALFNDKPR CONTINUE THROUGH OUT, FOR C=0, 1, C.GE.10OUT PRINT FORMAT PFMT, KPR(C*5+1), KPR(C*5+2), KPR(C*5+3), 0 KPR(C*5+4), KPR(C*5+5) END OF PROGRAM
K=1 K=2 K=3 K=4 K=5 2 4 8 16 32 3 6 12 24 48 5 9 18 36 72 7 10 20 40 80 11 14 27 54 108 13 15 28 56 112 17 21 30 60 120 19 22 42 81 162 23 25 44 84 168 29 26 45 88 176
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
k = 1: 2357111317192329k = 2: 46910141521222526k = 3: 8121820272830424445k = 4: 16243640545660818488k = 5: 32487280108112120162168176
/* Predicate function that checks k-almost primality for given integer n and parameter k */k_almost_primep(n,k):=ifintegerp((n)^(1/k))andprimep((n)^(1/k))thentrueelselambda([x],(length(ifactors(x))=kandunique(map(second,ifactors(x)))=[1])or(length(ifactors(x))<kandapply("+",map(second,ifactors(x)))=k))(n)$/* Function that given a parameter k1 returns the first len k1-almost primes */k_almost_prime_count(k1,len):=block(count:len,whilelength(sublist(makelist(i,i,count),lambda([x],k_almost_primep(x,k1))))<lendo(count:count+1),sublist(makelist(i,i,count),lambda([x],k_almost_primep(x,k1))))$/* Test cases */k_almost_prime_count(1,10);k_almost_prime_count(2,10);k_almost_prime_count(3,10);k_almost_prime_count(4,10);k_almost_prime_count(5,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]
primeFactory=function(n=2)ifn<2thenreturn""foriinrange(2,n)p=floor(n/i)q=n%iifnotqthenreturnstr(i)+" "+str(primeFactory(p))endforreturnnendfunctiongetAlmostPrimes=function(k)almost=[]n=2whilealmost.len<10primes=primeFactory(n).trim.splitifprimes.len==kthenalmost.push(n)n+=1endwhilereturnalmostendfunctionforiinrange(1,5)printi+": "+getAlmostPrimes(i)endfor
]run1: [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]
MODULEAlmostPrime;FROMFormatStringIMPORTFormatString;FROMTerminalIMPORTWriteString,WriteLn,ReadChar;PROCEDUREKPrime(n,k:INTEGER):BOOLEAN;VARp,f:INTEGER;BEGINf:=0;p:=2;WHILE(f<k)AND(p*p<=n)DOWHILEnMODp=0DOn:=nDIVp;INC(f)END;INC(p)END;IFn>1THENRETURNf+1=kEND;RETURNf=kENDKPrime;VARbuf:ARRAY[0..63]OFCHAR;i,c,k:INTEGER;BEGINFORk:=1TO5DOFormatString("k = %i:",buf,k);WriteString(buf);i:=2;c:=0;WHILEc<10DOIFKPrime(i,k)THENFormatString(" %i",buf,i);WriteString(buf);INC(c)END;INC(i)END;WriteLn;END;ReadChar;ENDAlmostPrime.
procprime(k:int,listLen:int):seq[int]=result=@[]vartest:int=2curseur:int=0whilecurseur<listLen:vari:int=2compte=0n=testwhilei<=n:if(nmodi)==0:n=ndivicompte+=1else:i+=1ifcompte==k:result.add(test)curseur+=1test+=1forkin1..5:echo"k = ",k," : ",prime(k,10)
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]
MODULEAlmostPrime;(* Show some k-almost-prime numbers - Translation of C Via Algol W *)IMPORTOut,Math;(* returns TRUE if nv is k-almost-prime, FALSE otherwise *)PROCEDUREkPrime(nv,k:INTEGER):BOOLEAN;VARp,f,n,rootN:INTEGER;BEGINn:=nv;f:=0;WHILE(f<=k)&~ODD(n)DOn:=nDIV2;INC(f)END;p:=3;rootN:=FLOOR(Math.sqrt(FLT(n)));WHILE(f<=k)&(p<=rootN)DOWHILEnMODp=0DOn:=nDIVp;INC(f)END;INC(p,2)END;IFn>1THENINC(f)END;RETURNf=kENDkPrime;(* Show n k-almost-prime numbers *)PROCEDUREshowKAlmostPrimes(k,n:INTEGER);VARc,i:INTEGER;BEGINOut.String("k = ");Out.Int(k,0);Out.String(": ");c:=0;i:=2;WHILEc<nDOIFkPrime(i,k)THENOut.String(" ");Out.Int(i,3);INC(c)END;INC(i)END;Out.LnENDshowKAlmostPrimes;BEGINshowKAlmostPrimes(1,10);showKAlmostPrimes(2,10);showKAlmostPrimes(3,10);showKAlmostPrimes(4,10);showKAlmostPrimes(5,10)ENDAlmostPrime.
k = 1: 2 3 5 7 11 13 17 19 23 29k = 2: 4 6 9 10 14 15 21 22 25 26k = 3: 8 12 18 20 27 28 30 42 44 45k = 4: 16 24 36 40 54 56 60 81 84 88k = 5: 32 48 72 80 108 112 120 162 168 176
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(); }; }}k = 1: 2 3 5 7 11 13 17 19 23 29k = 2: 4 6 9 10 14 15 21 22 25 26k = 3: 8 12 18 20 27 28 30 42 44 45k = 4: 16 24 36 40 54 56 60 81 84 88k = 5: 32 48 72 80 108 112 120 162 168 176
packagealmostprimeimport"core:fmt"main::proc(){i,c,k:intforkin1..=5{fmt.printf("k = %d:",k)fori,c:=2,0;c<10;i+=1{ifkprime(i,k){fmt.printf(" %v",i)c+=1}}fmt.printf("\n")}}kprime::proc(n:int,k:int)->bool{p,f:int=0,0n:=nforp:=2;f<k&&p*p<=n;p+=1{for(0==n%p){n/=pf+=1}}returnf+(n>1?1:0)==k}
k = 1: 2 3 5 7 11 13 17 19 23 29k = 2: 4 6 9 10 14 15 21 22 25 26k = 3: 8 12 18 20 27 28 30 42 44 45k = 4: 16 24 36 40 54 56 60 81 84 88k = 5: 32 48 72 80 108 112 120 162 168 176
: kprime?( n k -- b )| i | 0 2 n for: i [ while( n i /mod swap 0 = ) [ ->n 1+ ] drop ] k == ; : table( k -- [] )| l | Array new dup ->l 2 while (l size 10 <>) [ dup k kprime? if dup l add then 1+ ] drop ;
>#[ table .cr ] 5 each[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]
packagemainusecore{printf}main::()->void{printf("\n");forkin1..6{printf("k = {}:",k);i:=2;c:i32;whilec<10{ifkprime(i,k){printf(" {}",i);c+=1;}i+=1;}printf("\n");}}kprime::(n:i32,k:i32)->bool{f:i32;whilep:=2;f<k&&p*p<=n{whilen%p==0{n/=p;f+=1;}p+=1;}returnf+(1ifn>1else0)==k;}
k = 1: 2 3 5 7 11 13 17 19 23 29k = 2: 4 6 9 10 14 15 21 22 25 26k = 3: 8 12 18 20 27 28 30 42 44 45k = 4: 16 24 36 40 54 56 60 81 84 88k = 5: 32 48 72 80 108 112 120 162 168 176
//+optional-semicolonsusecore{printf}usecore.itermain::(){generator:=iter.counter(1)|>iter.map(k=>.{k=k,kprimes=kprime_iter(k)->take(10)})|>iter.take(5)forvalingenerator{printf("k = {}:",val.k)forpinval.kprimesdoprintf(" {}",p)printf("\n")}}kprime_iter::k=>iter.counter(2)|>iter.filter((i,[k])=>kprime(i,k))kprime::(n,k)=>{f:=0forpiniter.counter(2){iff>=kdobreakifp*p>ndobreakwhilen%p==0{n/=pf+=1}}returnf+(1ifn>1else0)==k}
k = 1: 2 3 5 7 11 13 17 19 23 29k = 2: 4 6 9 10 14 15 21 22 25 26k = 3: 8 12 18 20 27 28 30 42 44 45k = 4: 16 24 36 40 54 56 60 81 84 88k = 5: 32 48 72 80 108 112 120 162 168 176
almost(k)=my(n); for(i=1,10,while(bigomega(n++)!=k,); print1(n", "));for(k=1,5,almost(k);print)
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,
programAlmostPrime;{$IFDEF FPC}{$Mode Delphi}{$ENDIF}usesprimtrial;vari,K,cnt:longWord;BEGINK:=1;repeatcnt:=0;i:=2;write('K=',K:2,':');repeatifisAlmostPrime(i,K)thenBeginwrite(i:6,' ');inc(cnt);end;inc(i);untilcnt=9;writeln;inc(k);untilk>10;END.
K= 1 : 2 3 5 7 11 13 17 19 23 29K= 2 : 4 6 9 10 14 15 21 22 25 26K= 3 : 8 12 18 20 27 28 30 42 44 45K= 4 : 16 24 36 40 54 56 60 81 84 88K= 5 : 32 48 72 80 108 112 120 162 168 176K= 6 : 64 96 144 160 216 224 240 324 336 352K= 7 : 128 192 288 320 432 448 480 648 672 704K= 8 : 256 384 576 640 864 896 960 1296 1344 1408K= 9 : 512 768 1152 1280 1728 1792 1920 2592 2688 2816K=10 : 1024 1536 2304 2560 3456 3584 3840 5184 5376 5632
Using a CPAN module, which is simple and fast:
usentheoryqw/factor/;subalmost{my($k,$n)=@_;my$i=1;map{$i++whilescalarfactor($i)!=$k;$i++}1..$n;}say"$_ : ",join(" ",almost($_,10))for1..5;
1 : 2 3 5 7 11 13 17 19 23 292 : 4 6 9 10 14 15 21 22 25 263 : 8 12 18 20 27 28 30 42 44 454 : 16 24 36 40 54 56 60 81 84 885 : 32 48 72 80 108 112 120 162 168 176
or writing everything by hand:
usestrict;usewarnings;subk_almost_prime;formy$k(1..5){my$almost=0;printjoin(", ",map{1untilk_almost_prime++$almost,$k;"$almost";}1..10),"\n";}subnth_prime;subk_almost_prime{my($n,$k)=@_;returnif$n<=1or$k<1;my$which_prime=0;formy$count(1..$k){while($n%nth_prime$which_prime){++$which_prime;}$n/=nth_prime$which_prime;returnif$n==1and$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;subnth_prime{my$n=shift;returnif$n<0;OUTER:while($#primes<$n){while(my$s=delete$sieve{$candidate}){my$next=$s+$candidate;$next+=$swhileexists$sieve{$next};$sieve{$next}=$s;$candidate+=2;}while($candidate<$q){push@primes,$candidate;$candidate+=2;nextOUTERifexists$sieve{$candidate};}my$twop=2*$p;my$next=$q+$twop;$next+=$twopwhileexists$sieve{$next};$sieve{$next}=$twop;$p=$primes[++$p_iter];$q=$p*$p;$candidate+=2;}return$primes[$n];}}
2, 3, 5, 7, 11, 13, 17, 19, 23, 294, 6, 9, 10, 14, 15, 21, 22, 25, 268, 12, 18, 20, 27, 28, 30, 42, 44, 4516, 24, 36, 40, 54, 56, 60, 81, 84, 8832, 48, 72, 80, 108, 112, 120, 162, 168, 176
withjavascript_semanticssequenceres=columnize({tagset(5)})-- ie {{1},{2},{3},{4},{5}}integern=2,found=0whilefound<50dointegerl=length(prime_factors(n,true))ifl<=5andlength(res[l])<=10thenres[l]&=nfound+=1endifn+=1endwhilestringfmt="k = %d: "&join(repeat("%4d",10))&"\n"fori=1to5doprintf(1,fmt,res[i])endfor
k = 1: 2 3 5 7 11 13 17 19 23 29k = 2: 4 6 9 10 14 15 21 22 25 26k = 3: 8 12 18 20 27 28 30 42 44 45k = 4: 16 24 36 40 54 56 60 81 84 88k = 5: 32 48 72 80 108 112 120 162 168 176
/# Rosetta Code problem: http://rosettacode.org/wiki/Almost_primeby Galileo, 06/2022 #/include ..\Utilitys.pmtdef test tps over mod not enddefdef kprime? >ps >ps 0 ( 2 tps ) for test while tps over / int ps> drop >ps swap 1 + swap test endwhile drop endfor ps> drop ps> == enddef5 for >ps 2 ( ) len 10 < while over tps kprime? if over 0 put endif swap 1 + swap len 10 < endwhile nip ps> dropendforpstack
[[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]]=== Press any key to exit ===
<?php// Almost primefunctionisKPrime($n,$k){$f=0;for($j=2;$j<=$n;$j++){while($n%$j==0){if($f==$k)returnfalse;$f++;$n=floor($n/$j);}// while}// for $jreturn($f==$k);}for($k=1;$k<=5;$k++){echo"k = ",$k,":";$i=2;$c=0;while($c<10){if(isKPrime($i,$k)){echo" ",str_pad($i,3,' ',STR_PAD_LEFT);$c++;}$i++;}echoPHP_EOL;}?>
k = 1: 2 3 5 7 11 13 17 19 23 29k = 2: 4 6 9 10 14 15 21 22 25 26k = 3: 8 12 18 20 27 28 30 42 44 45k = 4: 16 24 36 40 54 56 60 81 84 88k = 5: 32 48 72 80 108 112 120 162 168 176
go => N = 10, Ps = primes(100).take(N), println(1=Ps), T = Ps, foreach(K in 2..5) T := mul_take(Ps,T,N), println(K=T) end, nl, foreach(K in 6..25) T := mul_take(Ps,T,N), println(K=T) end, nl.% take first N values of L1 x L2 mul_take(L1,L2,N) = [I*J : I in L1, J in L2, I<=J].sort_remove_dups().take(N).take(L,N) = [L[I] : I in 1..N].
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]6 = [64,96,144,160,216,224,240,324,336,352]7 = [128,192,288,320,432,448,480,648,672,704]8 = [256,384,576,640,864,896,960,1296,1344,1408]9 = [512,768,1152,1280,1728,1792,1920,2592,2688,2816]10 = [1024,1536,2304,2560,3456,3584,3840,5184,5376,5632]11 = [2048,3072,4608,5120,6912,7168,7680,10368,10752,11264]12 = [4096,6144,9216,10240,13824,14336,15360,20736,21504,22528]13 = [8192,12288,18432,20480,27648,28672,30720,41472,43008,45056]14 = [16384,24576,36864,40960,55296,57344,61440,82944,86016,90112]15 = [32768,49152,73728,81920,110592,114688,122880,165888,172032,180224]16 = [65536,98304,147456,163840,221184,229376,245760,331776,344064,360448]17 = [131072,196608,294912,327680,442368,458752,491520,663552,688128,720896]18 = [262144,393216,589824,655360,884736,917504,983040,1327104,1376256,1441792]19 = [524288,786432,1179648,1310720,1769472,1835008,1966080,2654208,2752512,2883584]20 = [1048576,1572864,2359296,2621440,3538944,3670016,3932160,5308416,5505024,5767168]21 = [2097152,3145728,4718592,5242880,7077888,7340032,7864320,10616832,11010048,11534336]22 = [4194304,6291456,9437184,10485760,14155776,14680064,15728640,21233664,22020096,23068672]23 = [8388608,12582912,18874368,20971520,28311552,29360128,31457280,42467328,44040192,46137344]24 = [16777216,25165824,37748736,41943040,56623104,58720256,62914560,84934656,88080384,92274688]25 = [33554432,50331648,75497472,83886080,113246208,117440512,125829120,169869312,176160768,184549376]
almost_prime: procedure options(main); kprime: procedure(nn, k) returns(bit); declare (n, nn, k, p, f) fixed; f = 0; n = nn; do p=2 repeat(p+1) while(f<k & p*p <= n); do n=n repeat(n/p) while(mod(n,p) = 0); f = f+1; end; end; return(f + (n>1) = k); end kprime; declare (i, c, k) fixed; do k=1 to 5; put edit('k = ',k,':') (A,F(1),A); c = 0; do i=2 repeat(i+1) while(c<10); if kprime(i,k) then do; put edit(i) (F(4)); c = c+1; end; end; put skip; end;end almost_prime;k = 1: 2 3 5 7 11 13 17 19 23 29k = 2: 4 6 9 10 14 15 21 22 25 26k = 3: 8 12 18 20 27 28 30 42 44 45k = 4: 16 24 36 40 54 56 60 81 84 88k = 5: 32 48 72 80 108 112 120 162 168 176
100H:BDOS: PROCEDURE (FN, ARG); DECLARE FN BYTE, ARG ADDRESS; GO TO 5; END BDOS;EXIT: PROCEDURE; CALL BDOS(0,0); END EXIT;PRINT: PROCEDURE (S); DECLARE S ADDRESS; CALL BDOS(9,S); END PRINT;PRINT$NUMBER: PROCEDURE (N); DECLARE S (4) BYTE INITIAL ('...$'); DECLARE P ADDRESS, (N, C BASED P) BYTE; P = .S(3);DIGIT: P = P - 1; C = N MOD 10 + '0'; N = N / 10; IF N > 0 THEN GO TO DIGIT; CALL PRINT(P);END PRINT$NUMBER;KPRIME: PROCEDURE (N, K) BYTE; DECLARE (N, K, P, F) BYTE; F = 0; P = 2; DO WHILE F < K AND P*P <= N; DO WHILE N MOD P = 0; N = N/P; F = F+1; END; P = P+1; END; IF N > 1 THEN F = F + 1; RETURN F = K;END KPRIME;DECLARE (I, C, K) BYTE;DO K=1 TO 5; CALL PRINT(.'K = $'); CALL PRINT$NUMBER(K); CALL PRINT(.':$'); C = 0; I = 2; DO WHILE C < 10; IF KPRIME(I, K) THEN DO; CALL PRINT(.' $'); CALL PRINT$NUMBER(I); C = C+1; END; I = I+1; END; CALL PRINT(.(13,10,'$'));END;CALL EXIT;EOFK = 1: 2 3 5 7 11 13 17 19 23 29K = 2: 4 6 9 10 14 15 21 22 25 26K = 3: 8 12 18 20 27 28 30 42 44 45K = 4: 16 24 36 40 54 56 60 81 84 88K = 5: 32 48 72 80 108 112 120 162 168 176
(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)
localfunctionk_prime(n,k)localnf=0fori=2,ndowhilen%i==0doifnf==kthenreturnfalseend++nfn//=iendendreturnnf==kendlocalfunctiongen(k,n)localr={}localm=2fori=1,ndowhile!k_prime(m,k)do++mendr[i]=mm+=1endreturnrendfork=1,5doprint($"{k}: {gen(k, 10):concat(",")}")end
1: 2, 3, 5, 7, 11, 13, 17, 19, 23, 292: 4, 6, 9, 10, 14, 15, 21, 22, 25, 263: 8, 12, 18, 20, 27, 28, 30, 42, 44, 454: 16, 24, 36, 40, 54, 56, 60, 81, 84, 885: 32, 48, 72, 80, 108, 112, 120, 162, 168, 176
# Converted from Ckprime = (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.
C and Potion take 0.006s, Perl5 0.028s
% 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 >= 2K1isK-1,almostPrime(K1,Take,Primes,L),multiplylist(Primes,L,Long),sort(Long,Sorted),% uniquifiestake(Take,Sorted,List).
That's it. The rest is machinery. For portability, a compatibility section is included below.
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),P2isPP+2,generate(P2,N),1isNmod2,% oddMaxisfloor(sqrt(N+1)),% round-off paranoiaforall((member(Prime,[2|Primes]),(Prime=<Max->true;(!,fail))),NmodPrime>0),!,P=N.% multiply( +A, +List, Answer )multiply(A,[],[]).multiply(A,[X|Xs],[AX|As]):-AXisA*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).
%%%%% 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.
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)
void setup() { for (int i = 1; i <= 5; i++) { int count = 0; print("k = " + i + ": "); int n = 2; while (count < 10) { if (isAlmostPrime(i, n)) { count++; print(n + " "); } n++; } println(); }}boolean isAlmostPrime(int k, int n) { if (countPrimeFactors(n) == k) { return true; } else { return false; }}int countPrimeFactors(int n) { int count = 0; int i = 2; while (n > 1) { if (n % i == 0) { n /= i; count++; } else { i++; } } return count;}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
This importsPrime decomposition#Python
fromprime_decompositionimportdecomposefromitertoolsimportislice,counttry:fromfunctoolsimportreduceexcept:passdefalmostprime(n,k=2):d=decompose(n)try:terms=[next(d)foriinrange(k)]returnreduce(int.__mul__,terms,1)==nexcept:returnFalseif__name__=='__main__':forkinrange(1,6):print('%i:%r'%(k,list(islice((nfornincount()ifalmostprime(n,k)),10))))
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]
# k-Almost-primes# Python 3.6.3# no imports# author: manuelcaeiro | https://github.com/manuelcaeirodefprime_factors(m=2):foriinrange(2,m):r,q=divmod(m,i)ifnotq:return[i]+prime_factors(r)return[m]defk_almost_primes(n,k=2):multiples=set()lists=list()forxinrange(k+1):lists.append([])foriinrange(2,n+1):ifinotinmultiples:iflen(lists[1])<10:lists[1].append(i)multiples.update(range(i*i,n+1,i))print("k=1:{}".format(lists[1]))forjinrange(2,k+1):forminmultiples:l=prime_factors(m)ll=len(l)ifll==jandlen(lists[j])<10:lists[j].append(m)print("k={}:{}".format(j,lists[j]))k_almost_primes(200,5)# try:#k_almost_primes(6000, 10)
>>> %Run k_almost_primes.pyk=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]
primefactors is defined atPrime decomposition#Quackery.
[ stack ] is quantity ( --> s ) [ stack ] is factors ( --> s ) [ factors put quantity put [] 1 [ over size quantity share != while 1+ dup primefactors size factors share = if [ tuck join swap ] again ] drop factors release quantity release ] is almostprimes ( n n --> [ ) 5 times [ 10 i^ 1+ dup echo sp almostprimes echo cr ]
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 ]
This uses the function fromPrime decomposition#R
#===============================================================# Find k-Almost-primes# R implementation#===============================================================#---------------------------------------------------------------# Function for prime factorization from Rosetta Code#---------------------------------------------------------------findfactors<-function(n){d<-c()div<-2;nxt<-3;rest<-nwhile(rest!=1){while(rest%%div==0){d<-c(d,div)rest<-floor(rest/div)}div<-nxtnxt<-nxt+2}d}#---------------------------------------------------------------# Find k-Almost-primes#---------------------------------------------------------------almost_primes<-function(n=10,k=5){# Set up matrix for storing of the resultsres<-matrix(NA,nrow=k,ncol=n)rownames(res)<-paste("k = ",1:k,sep="")colnames(res)<-rep("",n)# Loop over kfor(iin1:k){tmp<-1while(any(is.na(res[i,]))){# Keep looping if there are still missing entries in the result-matrixif(length(findfactors(tmp))==i){# Check number of factorsres[i,which.max(is.na(res[i,]))]<-tmp}tmp<-tmp+1}}print(res)}
k = 1 2 3 5 7 11 13 17 19 23 29k = 2 4 6 9 10 14 15 21 22 25 26k = 3 8 12 18 20 27 28 30 42 44 45k = 4 16 24 36 40 54 56 60 81 84 88k = 5 32 48 72 80 108 112 120 162 168 176
#langracket(require(only-inmath/number-theoryfactorize))(define((k-almost-prime?k)n)(=k(for/sum((f(factorizen)))(cadrf))))(defineKAP-table-values(for/list((k(in-range1(add15))))(definekap?(k-almost-prime?k))(for/list((j(in-range10))(i(sequence-filterkap?(in-naturals1))))i)))(define(format-tablet)(definelongest-number-length(add1(order-of-magnitude(argmaxorder-of-magnitude(cons(lengtht)(applyappendt))))))(define(fmt-valv)(~av#:widthlongest-number-length#:align'right))(string-join(for/list((rt)(k(in-naturals1)))(string-append(format"║ k = ~a║ "(fmt-valk))(string-join(for/list((cr))(fmt-valc))"| ")"║"))"\n"))(displayln(format-tableKAP-table-values))
║ 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║
(formerly Perl 6)
subis-k-almost-prime($niscopy,$k)returnsBool {loop (my ($p,$f) =2,0;$f <$k &&$p*$p <=$n;$p++) {$n /=$p,$f++while$n %%$p; }$f + ($n >1) ==$k;}for1 ..5 ->$k {say ~.[^10]givengrep {is-k-almost-prime($_,$k) },2 .. *}
2 3 5 7 11 13 17 19 23 294 6 9 10 14 15 21 22 25 268 12 18 20 27 28 30 42 44 4516 24 36 40 54 56 60 81 84 8832 48 72 80 108 112 120 162 168 176
Here is a solution with identical output based on thefactors routine fromCount_in_factors#Raku (to be included manually until we decide where in the distribution to put it).
constant@primes =2, |(3,5,7 ... *).grep: *.is-prime;multisubfactors(1) {1 }multisubfactors(Int$remainderiscopy) {gatherfor@primes ->$factor {# if remainder < factor², we're doneif$factor *$factor >$remainder {take$remainderif$remainder >1;last; }# How many times can we divide by this prime?while$remainder %%$factor {take$factor;lastif ($remainderdiv=$factor) ===1; } }}constant@factory =lazy0..*Z=>flat (0,0,map { +factors($_) },2..*);subalmost($n) {map *.key,grep *.value ==$n,@factory }putalmost($_)[^10]for1..5;
Modules:How to use
Modules:Source code
Function Factors in module Sequences finds all prime factors of a number. The result is used for generating the k almost primes.
--23Aug2025includeSettingsay'ALMOST PRIME'sayversionsayargnkmsay'Direct approach using Factors'numericdigits16ifn=''thenn=10ifk=''thenk=5/* Maximum number to examine */ifm=''thenm=180callTime('r')/* Collect almost primes */ap.=0doi=2tomf=Factors(i);ap.f.0=ap.f.0+1ap=ap.f.0;ap.f.ap=iend/* Show results */doi=1tokcallCharout,'k='i': 'doj=1tonifap.i.j>0thendocallCharout,ap.i.j' 'endendsayendsayFormat(Time('e'),,3)'seconds'exitincludeMath
The maximum number m is parameter here, but may be estimated from n and k.
ALMOST PRIME - 3 Mar 2025REXX-Regina_3.9.6(MT) 5.00 29 Apr 2024Direct approach using Factorsk=1: 2 3 5 7 11 13 17 19 23 29k=2: 4 6 9 10 14 15 21 22 25 26k=3: 8 12 18 20 27 28 30 42 44 45k=4: 16 24 36 40 54 56 60 81 84 88k=5: 32 48 72 80 108 112 120 162 168 1760.003 seconds
ALMOST PRIME - 3 Mar 2025REXX-Regina_3.9.6(MT) 5.00 29 Apr 2024Direct approach using Factorsk=1: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71k=2: 4 6 9 10 14 15 21 22 25 26 33 34 35 38 39 46 49 51 55 57k=3: 8 12 18 20 27 28 30 42 44 45 50 52 63 66 68 70 75 76 78 92k=4: 16 24 36 40 54 56 60 81 84 88 90 100 104 126 132 135 136 140 150 152k=5: 32 48 72 80 108 112 120 162 168 176 180 200 208 243 252 264 270 272 280 300k=6: 64 96 144 160 216 224 240 324 336 352 360 400 416 486 504 528 540 544 560 600k=7: 128 192 288 320 432 448 480 648 672 704 720 800 832 972 1008 1056 1080 1088 1120 1200k=8: 256 384 576 640 864 896 960 1296 1344 1408 1440 1600 1664 1944 2016 2112 2160 2176 2240 2400k=9: 512 768 1152 1280 1728 1792 1920 2592 2688 2816 2880 3200 3328 3888 4032 4224 4320 4352 4480 4800k=10: 1024 1536 2304 2560 3456 3584 3840 5184 5376 5632 5760 6400 6656 7776 8064 8448 8640 8704 8960 9600k=11: 2048 3072 4608 5120 6912 7168 7680 10368 10752 11264 11520 12800 13312 15552 16128 16896 17280 17408 17920 19200k=12: 4096 6144 9216 10240 13824 14336 15360 20736 21504 22528 23040 25600 26624 31104 32256 33792 34560 34816 35840 384000.885 seconds
ALMOST PRIME - 3 Mar 2025REXX-Regina_3.9.6(MT) 5.00 29 Apr 2024Direct approach using Factorsk=1: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71k=2: 4 6 9 10 14 15 21 22 25 26 33 34 35 38 39 46 49 51 55 57k=3: 8 12 18 20 27 28 30 42 44 45 50 52 63 66 68 70 75 76 78 92k=4: 16 24 36 40 54 56 60 81 84 88 90 100 104 126 132 135 136 140 150 152k=5: 32 48 72 80 108 112 120 162 168 176 180 200 208 243 252 264 270 272 280 300k=6: 64 96 144 160 216 224 240 324 336 352 360 400 416 486 504 528 540 544 560 600k=7: 128 192 288 320 432 448 480 648 672 704 720 800 832 972 1008 1056 1080 1088 1120 1200k=8: 256 384 576 640 864 896 960 1296 1344 1408 1440 1600 1664 1944 2016 2112 2160 2176 2240 2400k=9: 512 768 1152 1280 1728 1792 1920 2592 2688 2816 2880 3200 3328 3888 4032 4224 4320 4352 4480 4800k=10: 1024 1536 2304 2560 3456 3584 3840 5184 5376 5632 5760 6400 6656 7776 8064 8448 8640 8704 8960 9600k=11: 2048 3072 4608 5120 6912 7168 7680 10368 10752 11264 11520 12800 13312 15552 16128 16896 17280 17408 17920 19200k=12: 4096 6144 9216 10240 13824 14336 15360 20736 21504 22528 23040 25600 26624 31104 32256 33792 34560 34816 35840 38400k=13: 8192 12288 18432 20480 27648 28672 30720 41472 43008 45056 46080 51200 53248 62208 64512 67584 69120 69632 71680 76800k=14: 16384 24576 36864 40960 55296 57344 61440 82944 86016 90112 92160 102400 106496 124416 129024 135168 138240 139264 143360 153600k=15: 32768 49152 73728 81920 110592 114688 122880 165888 172032 180224 184320 204800 212992 248832 258048 270336 276480 278528 286720 307200k=16: 65536 98304 147456 163840 221184 229376 245760 331776 344064 360448 368640 409600 425984 497664 516096 540672 552960 557056 573440 61440025.129 seconds
Not too bad! By the way, Version 3 can also generate lists of almost prime over other number ranges. Say you change the first do in 'do 1000000 to m' and run as follows, you get
ALMOST PRIME - 3 Mar 2025REXX-Regina_3.9.6(MT) 5.00 29 Apr 2024Direct approach using Factorsk=1: 1000003 1000033 1000037 1000039 1000081 1000099 1000117 1000121 1000133 1000151k=2: 1000001 1000007 1000009 1000011 1000015 1000018 1000019 1000021 1000023 1000031k=3: 1000002 1000006 1000013 1000014 1000022 1000028 1000029 1000030 1000043 1000046k=4: 1000005 1000010 1000012 1000017 1000024 1000027 1000034 1000038 1000041 1000042k=5: 1000004 1000016 1000025 1000035 1000036 1000044 1000056 1000060 1000062 1000072k=6: 1000020 1000026 1000040 1000048 1000050 1000065 1000076 1000090 1000096 1000100k=7: 1000125 1000152 1000176 1000200 1000256 1000352 1000368 1000404 1000428 1000431k=8: 1000008 1000032 1000128 1000272 1000296 1000400 1000416 1000440 1000500 1000560k=9: 1000064 1000080 1000160 1000192 1000224 1000350 1000480 1000640 1000832 1000896k=10: 1000320 1000384 1000704 1000800 1001160 1001280 1001376 1001600 1001664 10019520.116 seconds
for ap = 1 to 5 see "k = " + ap + ":" aList = [] for n = 1 to 200 num = 0 for nr = 1 to n if n%nr=0 and isPrime(nr)=1 num = num + 1 pr = nr while true pr = pr * nr if n%pr = 0 num = num + 1 else exit ok end ok next if (ap = 1 and isPrime(n) = 1) or (ap > 1 and num = ap) add(aList, n) if len(aList)=10 exit ok ok next for m = 1 to len(aList) see " " + aList[m] next see nlnextfunc isPrime num if (num <= 1) return 0 ok if (num % 2 = 0 and num != 2) return 0 ok for i = 3 to floor(num / 2) -1 step 2 if (num % i = 0) return 0 ok next return 1
Output:
k = 1: 2 3 5 7 11 13 17 19 23 29k = 2: 4 6 9 10 14 15 21 22 25 26k = 3: 8 12 18 20 27 28 30 42 44 45k = 4: 16 24 36 40 54 56 60 81 84 88k = 5: 32 48 72 80 108 112 120 162 168 176
| RPL code | Comment |
|---|---|
≪ → k ≪ 0 1 SF 2 3 PICKFOR jWHILE OVER j MOD NOTREPEATIF DUP k ==THEN 1 CF OVER 'j' STOEND 1 + SWAP j / SWAPENDNEXT k == 1 FS? AND SWAP DROP≫ ≫ 'KPRIM' STO≪ 5 1FOR k { } 2WHILE OVER SIZE 10 <REPEATIF DUP kKPRIMTHEN SWAP OVER + SWAPEND 1 +END DROP -1STEP≫ 'TASK' STO | KPRIM( n k → boolean )Dim f As Integer = 0 For i As Integer = 2 To n While n Mod i = 0 If f = k Then Return false f += 1 n \= i Wend Next Return f = kEnd Function |
5 : { 32 48 72 80 108 112 120 162 168 176 }4 : { 16 24 36 40 54 56 60 81 84 88 }3 : { 8 12 18 20 27 28 30 42 44 45 }2 : { 4 6 9 10 14 15 21 22 25 26 }1 : { 2 3 5 7 9 11 13 17 19 23 29 }require'prime'defalmost_primes(k=2)returnto_enum(:almost_primes,k)unlessblock_given?1.step{|n|yieldnifn.prime_division.sum(&:last)==k}end(1..5).each{|k|putsalmost_primes(k).take(10).join(", ")}
2, 3, 5, 7, 11, 13, 17, 19, 23, 294, 6, 9, 10, 14, 15, 21, 22, 25, 268, 12, 18, 20, 27, 28, 30, 42, 44, 4516, 24, 36, 40, 54, 56, 60, 81, 84, 8832, 48, 72, 80, 108, 112, 120, 162, 168, 176
require'prime'par=pr=Prime.take(10)4.times{par=ar.product(pr).map{|(a,b)|a*b}.uniq.sort.take(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]
fnis_kprime(n:u32,k:u32)->bool{letmutprimes=0;letmutf=2;letmutrem=n;whileprimes<k&&rem>1{while(rem%f)==0&&rem>1{rem/=f;primes+=1;}f+=1;}rem==1&&primes==k}structKPrimeGen{k:u32,n:u32,}implIteratorforKPrimeGen{typeItem=u32;fnnext(&mutself)->Option<u32>{self.n+=1;while!is_kprime(self.n,self.k){self.n+=1;}Some(self.n)}}fnkprime_generator(k:u32)->KPrimeGen{KPrimeGen{k:k,n:1}}fnmain(){forkin1..6{println!("{}: {:?}",k,kprime_generator(k).take(10).collect::<Vec<_>>());}}
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]
defisKPrime(n:Int,k:Int,d:Int=2):Boolean=(n,k,d)match{case(n,k,_)ifn==1=>k==0case(n,_,d)ifn%d==0=>isKPrime(n/d,k-1,d)case(_,_,_)=>isKPrime(n,k,d+1)}defkPrimeStream(k:Int):Stream[Int]={defloop(n:Int):Stream[Int]=if(isKPrime(n,k))n#::loop(n+1)elseloop(n+1)loop(2)}for(k<-1to5){println(s"$k: [${kPrimeStream(k).take(10)mkString" "}]")}
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]
$ include "seed7_05.s7i";const func boolean: kprime (in var integer: number, in integer: k) is func result var boolean: kprime is FALSE; local var integer: p is 2; var integer: f is 0; begin while f < k and p * p <= number do while number rem p = 0 do number := number div p; incr(f); end while; incr(p); end while; kprime := f + ord(number > 1) = k; end func;const proc: main is func local var integer: k is 0; var integer: number is 0; var integer: count is 0; begin for k range 1 to 5 do write("k = " <& k <& ":"); count := 0; for number range 2 to integer.last until count >= 10 do if kprime(number, k) then write(" " <& number); incr(count); end if; end for; writeln; end for; end func;k = 1: 2 3 5 7 11 13 17 19 23 29k = 2: 4 6 9 10 14 15 21 22 25 26k = 3: 8 12 18 20 27 28 30 42 44 45k = 4: 16 24 36 40 54 56 60 81 84 88k = 5: 32 48 72 80 108 112 120 162 168 176
import <Utilities/Conversion.sl>;import <Utilities/Sequence.sl>;main(args(2)) :=letresult := firstNKPrimes(1 ... 5, 10);output[i] := "k = " ++ intToString(i) ++ ": " ++ delimit(intToString(result[i]), ' ');indelimit(output, '\n');firstNKPrimes(k, N) := firstNKPrimesHelper(k, N, 2, []);firstNKPrimesHelper(k, N, current, result(1)) :=letnewResult := result when not isKPrime(k, current) else result ++ [current]; inresult when size(result) = NelsefirstNKPrimesHelper(k, N, current + 1, newResult);isKPrime(k, n) := size(primeFactorization(n)) = k;
Using Prime Decomposition Solution[1]
main.exe"k = 1: 2 3 5 7 11 13 17 19 23 29k = 2: 4 6 9 10 14 15 21 22 25 26k = 3: 8 12 18 20 27 28 30 42 44 45k = 4: 16 24 36 40 54 56 60 81 84 88k = 5: 32 48 72 80 108 112 120 162 168 176"
Efficient algorithm for generating all the k-almost prime numbers in a given range[a,b]:
funcalmost_primes(a,b,k){a=max(2**k,a)vararr=[]func(m,lo,k){varhi=idiv(b,m).iroot(k)if(k==1){lo=max(lo,idiv_ceil(a,m))each_prime(lo,hi,{|p|arr<<m*p})returnnil}each_prime(lo,hi,{|p|vart=m*pvaru=idiv_ceil(a,t)varv=idiv(b,t)nextif(u>v)__FUNC__(t,p,k-1)})}(1,2,k)returnarr.sort}forkin(1..5){var(x=10,lo=1,hi=2)vararr=[]loop{arr+=almost_primes(lo,hi,k)breakif(arr.len>=x)lo=hi+1hi=2*lo}sayarr.first(x)}
[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]
Also built-in:
forkin(1..5){varx=10sayk.almost_primes(x.nth_almost_prime(k))}
(same output as above)
structKPrimeGen:Sequence,IteratorProtocol{letk:Intprivate(set)varn:IntprivatefuncisKPrime()->Bool{varprimes=0varf=2varrem=nwhileprimes<k&&rem>1{whilerem%f==0&&rem>1{rem/=fprimes+=1}f+=1}returnrem==1&&primes==k}mutatingfuncnext()->Int?{n+=1while!isKPrime(){n+=1}returnn}}forkin1..<6{print("\(k):\(Array(KPrimeGen(k:k,n:1).lazy.prefix(10)))")}
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]
packagerequireTcl8.6packagerequiremath::numtheoryprocfirstNprimesn{for{setresult{};seti2}{[llength$result]<$n}{incri}{if{[::math::numtheory::isprime$i]}{lappendresult$i}}return$result}procfirstN_KalmostPrimes{nk}{setp[firstNprimes$n]seti[lrepeat$k0]setc{}whiletrue{dictsetc[::tcl::mathop::*{*}[lmapj$i{lindex$p$j}]]""for{setx0}{$x<$k}{incrx}{lseti$x[setxx[expr{([lindex$i$x]+1)%$n}]]if{$xx}break}if{$x==$k}break}return[lrange[lsort-integer[dictkeys$c]]0[expr{$n-1}]]}for{setK1}{$K<=5}{incrK}{puts"$K => [firstN_KalmostPrimes 10 $K]"}
1 => 2 3 5 7 11 13 17 19 23 292 => 4 6 9 10 14 15 21 22 25 263 => 8 12 18 20 27 28 30 42 44 454 => 16 24 36 40 54 56 60 81 84 885 => 32 48 72 80 108 112 120 162 168 176
// Almost primefunctionisKPrime(n:number,k:number):bool{varf=0;for(vari=2;i<=n;i++)while(n%i==0){if(f==k)returnfalse;++f;n=Math.floor(n/i);}returnf==k;}for(vark=1;k<=5;k++){process.stdout.write(`k =${k}:`);vari=2,c=0;while(c<10){if(isKPrime(i,k)){process.stdout.write(" "+i.toString().padStart(3,' '));++c;}++i;}console.log();}
k = 1: 2 3 5 7 11 13 17 19 23 29k = 2: 4 6 9 10 14 15 21 22 25 26k = 3: 8 12 18 20 27 28 30 42 44 45k = 4: 16 24 36 40 54 56 60 81 84 88k = 5: 32 48 72 80 108 112 120 162 168 176
▽⊸(=⊣⊸°/×)↘2⇡30≡⌟(↙10⍆≡/×⧅≤)+1⇡5
╭─ ╷ 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 ╯
PrivateFunctionkprime(ByValnAsInteger,kAsInteger)AsBooleanDimpAsInteger,factorsAsIntegerp=2factors=0DoWhilefactors<kAndp*p<=nDoWhilenModp=0n=n/pfactors=factors+1Loopp=p+1Loopfactors=factors-(n>1)'true=-1kprime=factors=kEndFunctionPrivateSubalmost_primeC()DimnextkprimeAsInteger,countAsIntegerDimkAsIntegerFork=1To5Debug.Print"k =";k;":";nextkprime=2count=0DoWhilecount<10Ifkprime(nextkprime,k)ThenDebug.Print" ";Format(CStr(nextkprime),"@@@@@");count=count+1EndIfnextkprime=nextkprime+1LoopDebug.PrintNextkEndSub
k = 1 : 2 3 5 7 11 13 17 19 23 29k = 2 : 4 6 9 10 14 15 21 22 25 26k = 3 : 8 12 18 20 27 28 30 42 44 45k = 4 : 16 24 36 40 54 56 60 81 84 88k = 5 : 32 48 72 80 108 112 120 162 168 176
Repurposed the VBScript code for the Prime Decomposition task.
Fork=1To5count=0increment=1WScript.StdOut.Write"K"&k&": "DoUntilcount=10IfPrimeFactors(increment)=kThenWScript.StdOut.Writeincrement&" "count=count+1EndIfincrement=increment+1LoopWScript.StdOut.WriteLineNextFunctionPrimeFactors(n)PrimeFactors=0arrP=Split(ListPrimes(n)," ")divnum=nDoUntildivnum=1Fori=0ToUBound(arrP)-1Ifdivnum=1ThenExitForElseIfdivnumModarrP(i)=0Thendivnum=divnum/arrP(i)PrimeFactors=PrimeFactors+1EndIfNextLoopEndFunctionFunctionIsPrime(n)Ifn=2ThenIsPrime=TrueElseIfn<=1OrnMod2=0ThenIsPrime=FalseElseIsPrime=TrueFori=3ToInt(Sqr(n))Step2IfnModi=0ThenIsPrime=FalseExitForEndIfNextEndIfEndFunctionFunctionListPrimes(n)ListPrimes=""Fori=1TonIfIsPrime(i)ThenListPrimes=ListPrimes&i&" "EndIfNextEndFunction
K1: 2 3 5 7 11 13 17 19 23 29 K2: 4 6 9 10 14 15 21 22 25 26 K3: 8 12 18 20 27 28 30 42 44 45 K4: 16 24 36 40 54 56 60 81 84 88 K5: 32 48 72 80 108 112 120 162 168 176
fnk_prime(nint,kint)bool{mutnf:=0mutnn:=nforiin2..nn+1{fornn%i==0{ifnf==k{returnfalse}nf++nn/=i}}returnnf==k}fngen(kint,nint)[]int{mutr:=[]int{len:n}mutnx:=2foriin0..n{for!k_prime(nx,k){nx++}r[i]=nxnx++}returnr}fnmain(){forkin1..6{println("$k ${gen(k,10)}")}}
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]
varkPrime=Fn.new{|n,k|varnf=0vari=2while(i<=n){while(n%i==0){if(nf==k)returnfalsenf=nf+1n=(n/i).floor}i=i+1}returnnf==k}vargen=Fn.new{|k,n|varr=List.filled(n,0)n=2for(iin0...r.count){while(!kPrime.call(n,k))n=n+1r[i]=nn=n+1}returnr}for(kin1..5)System.print("%(k)%(gen.call(k,10))")
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]
func Factors(N); \Return number of (prime) factors in Nint N, F, C;[C:= 0; F:= 2;repeat if rem(N/F) = 0 then [C:= C+1; N:= N/F; ] else F:= F+1;until F > N;return C;];int K, C, N;[for K:= 1 to 5 do [C:= 0; N:= 2; IntOut(0, K); Text(0, ": "); loop [if Factors(N) = K then [IntOut(0, N); ChOut(0, ^ ); C:= C+1; if C >= 10 then quit; ]; N:= N+1; ]; CrLf(0); ];]
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
Using the prime generator from taskExtensible prime generator#zkl.
Can't say I entirely understand this algorithm. Uses list comprehension to calculate the outer/tensor product (p10 ⊗ ar).
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();}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)