A number is an attractive number if the number of its prime factors (whether distinct or not) is also prime.
The number 20, whose prime decomposition is 2 × 2 × 5, is an attractive number because the number of its prime factors (3) is also prime.
Show sequence items up to 120.
F is_prime(n) I n < 2 R 0B L(i) 2 .. Int(sqrt(n)) I n % i == 0 R 0B R 1BF get_pfct(=n) V i = 2 [Int] factors L i * i <= n I n % i i++ E n I/= i factors.append(i) I n > 1 factors.append(n) R factors.len[Int] poolL(each) 0..120 pool.append(get_pfct(each))[Int] rL(each) pool I is_prime(each) r.append(L.index)print(r.map(String).join(‘,’))
4,6,8,9,10,12,14,15,18,20,21,22,25,26,27,28,30,32,33,34,35,38,39,42,44,45,46,48,49,50,51,52,55,57,58,62,63,65,66,68,69,70,72,74,75,76,77,78,80,82,85,86,87,91,92,93,94,95,98,99,102,105,106,108,110,111,112,114,115,116,117,118,119,120
;;; Show attractive numbers up to 120MAX:equ120; can be up to 255 (8 bit math is used);;;CP/M callsputs:equ9bdos:equ5org100h;;;-- Zero memory ------------------------------------------------lxib,fctrs; page 2mvie,2; zero out two pagesxraamovd,azloop:staxbinxbdcrdjnzzloopdcrejnzzloop;;; -- Generate primes --------------------------------------------lxih,plist; pointer to beginning of primes listmvie,2; first prime is 2pstore:movm,e; begin prime listpcand:inre; next candidatejzfactor; if 0, we've rolled over, so we're donemovl,d; beginning of primes list (D=0 here)movc,m; C = prime to test againstptest:mova,eploop:subc; test by repeated subtractionjcnotdiv; if carry, not divisiblejzpcand; if zero, next candidatejmpploopnotdiv:inxh; get next primemovc,mmova,c; is it zero?oraajnzptest; if not, test against next primejmppstore; otherwise, add E to the list of primes;;;-- Count factors ----------------------------------------------factor:mvic,2; start with twofnum:mvia,MAX; is candidate beyond maximum?cmpcjcoutput; then stop mvid,0; D = number of factors of Cmovl,d; L = first prime move,c; E = number we're factorizingfprim:mvih,ppage; H = current primemovh,mftest:mvib,0mova,ecpi1; If one, we've counted all the factorsjznxtfacfdiv:subhjzdivijcndiviinrbjmpfdivdivi:inrd; we found a factorinrbmove,b; we've removed it, try againjmpftestndivi:inrl; not divisible, try next primejmpfprim nxtfac:mova,d; store amount of factorsmvib,fcpagestaxbinrc; do next numberjmpfnum ;;;-- Check which numbers are attractive and print them ----------output:lxib,fctrs+2; start with twomvih,ppage; H = page of primesonum:mvia,MAX; is candidate beyond maximum?cmpcrc; then stopldaxb; get amount of factorsmvil,0; start at beginning of prime listchprm:cmp m; check against current primejzprint; if it's prime, then print the numberinrl; otherwise, check next primejpchprmnext:inrc; check next numberjmponumprint:pushb; keep registerspushhmova,c; print numbercallprintapoph; restore registerspopbjmpnext;;;Subroutine: print the number in Aprinta:lxid,num; DE = stringmvib,10; divisordigit:mvic,-1; C = quotientdivlp:inrcsubbjncdivlpadi'0'+10; make digitdcxd; store digitstaxdmova,c; again with new quotientoraa; is it zero?jnzdigit; if not, do next digitmvic,puts; CP/M print string (in DE)jmpbdosdb'000'; placeholder for numbernum:db' $'fcpage:equ2; factors in page 2ppage:equ3; primes in page 3fctrs:equ256*fcpageplist:equ256*ppage
4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
HOW TO RETURN factors n: PUT {} IN factors PUT 2 IN factor WHILE n >= factor: SELECT: n mod factor = 0: INSERT factor IN factors PUT n/factor IN n ELSE: PUT factor+1 IN factor RETURN factorsHOW TO REPORT attractive n: REPORT 1 = #factors #factors nPUT 0 IN colFOR i IN {1..120}: IF attractive i: WRITE i>>5 PUT col+1 IN col IF col mod 10=0: WRITE /4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
INCLUDE "H6:SIEVE.ACT"BYTE FUNC IsAttractive(BYTE n BYTE ARRAY primes) BYTE count,f IF n<=1 THEN RETURN (0) ELSEIF primes(n) THEN RETURN (0) FI count=0 f=2 DO IF n MOD f=0 THEN count==+1 n==/f IF n=1 THEN EXIT ELSEIF primes(n) THEN f=n FI ELSEIF f>=3 THEN f==+2 ELSE f=3 FI OD IF primes(count) THEN RETURN (1) FIRETURN (0)PROC Main() DEFINE MAX="120" BYTE ARRAY primes(MAX+1) BYTE i Put(125) PutE() ;clear the screen Sieve(primes,MAX+1) PrintF("Attractive numbers in range 1..%B:%E",MAX) FOR i=1 TO MAX DO IF IsAttractive(i,primes) THEN PrintF("%B ",i) FI ODRETURNScreenshot from Atari 8-bit computer
Attractive numbers in range 1..120:4 6 8 9 10 12 14 15 18 20 21 22 25 2627 28 30 32 33 34 35 38 39 42 44 45 4648 49 50 51 52 55 57 58 62 63 65 66 6869 70 72 74 75 76 77 78 80 82 85 86 8791 92 93 94 95 98 99 102 105 106 108110 111 112 114 115 116 117 118 119 120
withAda.Text_IO;procedureAttractive_NumbersisfunctionIs_Prime(N:inNatural)returnBooleanisD:Natural:=5;beginifN<2thenreturnFalse;endif;ifNmod2=0thenreturnN=2;endif;ifNmod3=0thenreturnN=3;endif;whileD*D<=NloopifNmodD=0thenreturnFalse;endif;D:=D+2;ifNmodD=0thenreturnFalse;endif;D:=D+4;endloop;returnTrue;endIs_Prime;functionCount_Prime_Factors(N:inNatural)returnNaturalisNC:Natural:=N;Count:Natural:=0;F:Natural:=2;beginifNC=1thenreturn0;endif;ifIs_Prime(NC)thenreturn1;endif;loopifNCmodF=0thenCount:=Count+1;NC:=NC/F;ifNC=1thenreturnCount;endif;ifIs_Prime(NC)thenF:=NC;endif;elsifF>=3thenF:=F+2;elseF:=3;endif;endloop;endCount_Prime_Factors;procedureShow_Attractive(Max:inNatural)isuseAda.Text_IO;packageInteger_IOis newAda.Text_IO.Integer_IO(Integer);N:Natural;Count:Natural:=0;beginPut_Line("The attractive numbers up to and including "&Max'Image&" are:");forIin1..MaxloopN:=Count_Prime_Factors(I);ifIs_Prime(N)thenInteger_IO.Put(I,Width=>5);Count:=Count+1;ifCountmod20=0thenNew_Line;endif;endif;endloop;endShow_Attractive;beginShow_Attractive(Max=>120);endAttractive_Numbers;
The attractive numbers up to and including 120 are: 4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
BEGIN # find some attractive numbers - numbers whose prime factor counts are # # prime, n must be > 1 # PR read "primes.incl.a68" PR # find the attractive numbers # INT max number = 120; []BOOL sieve = PRIMESIEVE ENTIER sqrt( max number ); print( ( "The attractve numbers up to ", whole( max number, 0 ), newline ) ); INT a count := 0; FOR i FROM 2 TO max number DO IF INT v := i; INT f count := 0; WHILE NOT ODD v DO f count +:= 1; v OVERAB 2 OD; FOR j FROM 3 BY 2 TO max number WHILE v > 1 DO WHILE v > 1 AND v MOD j = 0 DO f count +:= 1; v OVERAB j OD OD; f count > 0 THEN IF sieve[ f count ] THEN print( ( " ", whole( i, -3 ) ) ); IF ( a count +:= 1 ) MOD 20 = 0 THEN print( ( newline ) ) FI FI FI OD; print( ( newline, "Found ", whole( a count, 0 ), " attractive numbers", newline ) )END
The attractve numbers up to 120 4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120Found 74 attractive numbers
% find some attractive numbers - numbers whose prime factor count is prime %begin % implements the sieve of Eratosthenes % % s(i) is set to true if i is prime, false otherwise % % algol W doesn't have a upb operator, so we pass the size of the % % array in n % procedure sieve( logical array s ( * ); integer value n ) ; begin % start with everything flagged as prime % for i := 1 until n do s( i ) := true; % sieve out the non-primes % s( 1 ) := false; for i := 2 until truncate( sqrt( n ) ) do begin if s( i ) then for p := i * i step i until n do s( p ) := false end for_i ; end sieve ; % returns the count of prime factors of n, using the sieve of primes s % % n must be greater than 0 % integer procedure countPrimeFactors ( integer value n; logical array s ( * ) ) ; if s( n ) then 1 else begin integer count, rest; rest := n; count := 0; while rest rem 2 = 0 do begin count := count + 1; rest := rest div 2 end while_divisible_by_2 ; for factor := 3 step 2 until n - 1 do begin if s( factor ) then begin while rest > 1 and rest rem factor = 0 do begin count := count + 1; rest := rest div factor end while_divisible_by_factor end if_prime_factor end for_factor ; count end countPrimeFactors ; % maximum number for the task % integer maxNumber; maxNumber := 120; % show the attractive numbers % begin logical array s ( 1 :: maxNumber ); sieve( s, maxNumber ); i_w := 2; % set output field width % s_w := 1; % and output separator width % % find and display the attractive numbers % for i := 2 until maxNumber do if s( countPrimeFactors( i, s ) ) then writeon( i ) endend.
4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
onisPrime(n)if(n<4)thenreturn(n>1)if((nmod2is0)or(nmod3is0))thenreturnfalserepeatwithifrom5to(n^0.5)div1by6if((nmodiis0)or(nmod(i+2)is0))thenreturnfalseendrepeatreturntrueendisPrimeonprimeFactorCount(n)setxtonsetcounterto0if(n>1)thenrepeatwhile(nmod2=0)setcountertocounter+1setntondiv2endrepeatrepeatwhile(nmod3=0)setcountertocounter+1setntondiv3endrepeatsetito5setlimitto(n^0.5)div1repeatuntil(i>limit)repeatwhile(nmodi=0)setcountertocounter+1setntondiviendrepeattell(i+2)torepeatwhile(nmodit=0)setcountertocounter+1setntondivitendrepeatsetitoi+6setlimitto(n^0.5)div1endrepeatif(n>1)thensetcountertocounter+1endifreturncounterendprimeFactorCount-- Task code:localoutput,nsetoutputto{}repeatwithnfrom1to120if(isPrime(primeFactorCount(n)))thensetendofoutputtonendrepeatreturnoutput
{4,6,8,9,10,12,14,15,18,20,21,22,25,26,27,28,30,32,33,34,35,38,39,42,44,45,46,48,49,50,51,52,55,57,58,62,63,65,66,68,69,70,72,74,75,76,77,78,80,82,85,86,87,91,92,93,94,95,98,99,102,105,106,108,110,111,112,114,115,116,117,118,119,120}
It's possible of course to dispense with the isPrime() handler and instead use primeFactorCount() to count the prime factors of its own output, with 1 indicating an attractive number. The loss of performance only begins to become noticeable in the unlikely event of needing 300,000 or more such numbers!
attractive?:function[x]->prime?sizefactors.primexprintselect1..120=>attractive?
4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
AttractiveNumbers(n){c:=prime_numbers(n).count()ifc=1returnreturnisPrime(c)}isPrime(n){return(prime_numbers(n).count()=1)}prime_numbers(n){if(n<=3)return[n]ans:=[]done:=falsewhile!done{if!Mod(n,2){ans.push(2)n/=2continue}if!Mod(n,3){ans.push(3)n/=3continue}if(n=1)returnanssr:=sqrt(n)done:=true ; try to divide the checked number by all numbers till its square root.i:=6while(i<=sr+6){if!Mod(n,i-1){ ; is n divisible by i-1?ans.push(i-1)n/=i-1done:=falsebreak}if!Mod(n,i+1){ ; is n divisible by i+1?ans.push(i+1)n/=i+1done:=falsebreak}i+=6}}ans.push(n)returnans}
Examples:
c:=0loop{ifAttractiveNumbers(A_Index)c++,result.=SubStr(" "A_Index,-2).(Mod(c,20)?" ":"`n")ifA_Index=120break}MsgBox,262144,,%resultreturn
4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99102 105 106 108 110 111 112 114 115 116 117 118 119 120
# syntax: GAWK -f ATTRACTIVE_NUMBERS.AWK# converted from CBEGIN{limit=120printf("attractive numbers from 1-%d:\n",limit)for(i=1;i<=limit;i++){n=count_prime_factors(i)if(is_prime(n)){printf("%d ",i)}}printf("\n")exit(0)}functioncount_prime_factors(n,count,f){f=2if(n==1){return(0)}if(is_prime(n)){return(1)}while(1){if(!(n%f)){count++n/=fif(n==1){return(count)}if(is_prime(n)){f=n}}elseif(f>=3){f+=2}else{f=3}}}functionis_prime(x,i){if(x<=1){return(0)}for(i=2;i<=int(sqrt(x));i++){if(x%i==0){return(0)}}return(1)}
attractive numbers from 1-120:4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
10DEFINTA-Z20M=12030DIMC(M):C(0)=-1:C(1)=-140FORI=2TOSQR(M)50IFNOTC(I)THENFORJ=I+ITOMSTEPI:C(J)=-1:NEXT60NEXT70FORI=2TOM80N=I:C=090FORJ=2TOM100IFNOTC(J)THENIFNMODJ=0THENN=N\J:C=C+1:GOTO100110NEXT120IFNOTC(C)THENPRINTI,130NEXT
4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
get "libhdr"manifest $( MAXIMUM = 120 $) let sieve(prime, max) be$( for i=0 to max do i!prime := i>=2 for i=2 to max>>1 if i!prime $( let j = i<<1 while j <= max do $( j!prime := false j := j+i $) $)$)let factors(n, prime, max) = valof$( let count = 0 for i=2 to max if i!prime until n rem i $( count := count + 1 n := n / i $) resultis count$)let start() be$( let n = 0 and prime = vec MAXIMUM sieve(prime, MAXIMUM) for i=2 to MAXIMUM if factors(i, prime, MAXIMUM)!prime $( writed(i, 4) n := n + 1 unless n rem 18 do wrch('*N') $) wrch('*N')$)4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
#include<stdio.h>#define TRUE 1#define FALSE 0#define MAX 120typedefintbool;boolis_prime(intn){intd=5;if(n<2)returnFALSE;if(!(n%2))returnn==2;if(!(n%3))returnn==3;while(d*d<=n){if(!(n%d))returnFALSE;d+=2;if(!(n%d))returnFALSE;d+=4;}returnTRUE;}intcount_prime_factors(intn){intcount=0,f=2;if(n==1)return0;if(is_prime(n))return1;while(TRUE){if(!(n%f)){count++;n/=f;if(n==1)returncount;if(is_prime(n))f=n;}elseif(f>=3)f+=2;elsef=3;}}intmain(){inti,n,count=0;printf("The attractive numbers up to and including %d are:\n",MAX);for(i=1;i<=MAX;++i){n=count_prime_factors(i);if(is_prime(n)){printf("%4d",i);if(!(++count%20))printf("\n");}}printf("\n");return0;}
The attractive numbers up to and including 120 are: 4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
usingSystem;namespaceAttractiveNumbers{classProgram{constintMAX=120;staticboolIsPrime(intn){if(n<2)returnfalse;if(n%2==0)returnn==2;if(n%3==0)returnn==3;intd=5;while(d*d<=n){if(n%d==0)returnfalse;d+=2;if(n%d==0)returnfalse;d+=4;}returntrue;}staticintPrimeFactorCount(intn){if(n==1)return0;if(IsPrime(n))return1;intcount=0;intf=2;while(true){if(n%f==0){count++;n/=f;if(n==1)returncount;if(IsPrime(n))f=n;}elseif(f>=3){f+=2;}else{f=3;}}}staticvoidMain(string[]args){Console.WriteLine("The attractive numbers up to and including {0} are:",MAX);inti=1;intcount=0;while(i<=MAX){intn=PrimeFactorCount(i);if(IsPrime(n)){Console.Write("{0,4}",i);if(++count%20==0)Console.WriteLine();}++i;}Console.WriteLine();}}}
The attractive numbers up to and including 120 are: 4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
#include<iostream>#include<iomanip>#define MAX 120usingnamespacestd;boolis_prime(intn){if(n<2)returnfalse;if(!(n%2))returnn==2;if(!(n%3))returnn==3;intd=5;while(d*d<=n){if(!(n%d))returnfalse;d+=2;if(!(n%d))returnfalse;d+=4;}returntrue;}intcount_prime_factors(intn){if(n==1)return0;if(is_prime(n))return1;intcount=0,f=2;while(true){if(!(n%f)){count++;n/=f;if(n==1)returncount;if(is_prime(n))f=n;}elseif(f>=3)f+=2;elsef=3;}}intmain(){cout<<"The attractive numbers up to and including "<<MAX<<" are:"<<endl;for(inti=1,count=0;i<=MAX;++i){intn=count_prime_factors(i);if(is_prime(n)){cout<<setw(4)<<i;if(!(++count%20))cout<<endl;}}cout<<endl;return0;}
The attractive numbers up to and including 120 are: 4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
sieve = proc (max: int) returns (array[bool]) prime: array[bool] := array[bool]$fill(1,max,true) prime[1] := false for p: int in int$from_to(2, max/2) do if prime[p] then for c: int in int$from_to_by(p*p, max, p) do prime[c] := false end end end return(prime)end sieven_factors = proc (n: int, prime: array[bool]) returns (int) count: int := 0 i: int := 2 while i<=n do if prime[i] then while n//i=0 do count := count + 1 n := n/i end end i := i + 1 end return(count)end n_factorsstart_up = proc () MAX = 120 po: stream := stream$primary_output() prime: array[bool] := sieve(MAX) col: int := 0 for i: int in int$from_to(2, MAX) do if prime[n_factors(i,prime)] then stream$putright(po, int$unparse(i), 4) col := col + 1 if col//15 = 0 then stream$putl(po, "") end end endend start_up
4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
IDENTIFICATIONDIVISION.PROGRAM-ID.ATTRACTIVE-NUMBERS.DATADIVISION.WORKING-STORAGESECTION.77MAXIMUMPIC 999VALUE120.01SIEVE-DATAVALUESPACES.03MARKERPIC XOCCURS120TIMES.88PRIMEVALUESPACE.03SIEVE-MAXPIC 999.03COMPOSITEPIC 999.03CANDIDATEPIC 999.01FACTORIZE-DATA.03FACTOR-NUMPIC 999.03FACTORSPIC 999.03FACTORPIC 999.03QUOTIENTPIC 999V999.03FILLERREDEFINESQUOTIENT.05FILLERPIC 999.05DECIMALPIC 999.01OUTPUT-FORMAT.03OUT-NUMPIC ZZZ9.03OUT-LINEPIC X(72)VALUESPACES.03COL-PTRPIC 99VALUE1.PROCEDUREDIVISION.BEGIN.PERFORMSIEVE.PERFORMCHECK-ATTRACTIVEVARYINGCANDIDATEFROM2BY1UNTILCANDIDATEISGREATERTHANMAXIMUM.PERFORMWRITE-LINE.STOPRUN.CHECK-ATTRACTIVE.MOVECANDIDATETOFACTOR-NUM.PERFORMFACTORIZE.IFPRIME(FACTORS),PERFORMADD-TO-OUTPUT.ADD-TO-OUTPUT.MOVECANDIDATETOOUT-NUM.STRINGOUT-NUMDELIMITEDBYSIZEINTOOUT-LINEWITHPOINTERCOL-PTR.IFCOL-PTRISEQUALTO73,PERFORMWRITE-LINE.WRITE-LINE.DISPLAYOUT-LINE.MOVESPACESTOOUT-LINE.MOVE1TOCOL-PTR.FACTORIZESECTION.BEGIN.MOVEZEROTOFACTORS.PERFORMDIVIDE-PRIMEVARYINGFACTORFROM2BY1UNTILFACTORISGREATERTHANMAXIMUM.GOTODONE.DIVIDE-PRIME.IFPRIME(FACTOR),DIVIDEFACTOR-NUMBYFACTORGIVINGQUOTIENT,IFDECIMALISEQUALTOZERO,ADD1TOFACTORS,MOVEQUOTIENTTOFACTOR-NUM,GOTODIVIDE-PRIME.DONE.EXIT.SIEVESECTION.BEGIN.MOVE'X'TOMARKER(1).DIVIDEMAXIMUMBY2GIVINGSIEVE-MAX.PERFORMSET-COMPOSITESTHRUSET-COMPOSITES-LOOPVARYINGCANDIDATEFROM2BY1UNTILCANDIDATEISGREATERTHANSIEVE-MAX.GOTODONE.SET-COMPOSITES.MULTIPLYCANDIDATEBY2GIVINGCOMPOSITE.SET-COMPOSITES-LOOP.IFCOMPOSITEISNOTGREATERTHANMAXIMUM,MOVE'X'TOMARKER(COMPOSITE),ADDCANDIDATETOCOMPOSITE,GOTOSET-COMPOSITES-LOOP.DONE.EXIT.
4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
0010FUNCfactors#(n#)CLOSED0020count#:=00030WHILEn#MOD2=0DOn#:=n#DIV2;count#:+10040fac#:=30050WHILEfac#<=n#DO0060WHILEn#MODfac#=0DOn#:=n#DIVfac#;count#:+10070fac#:+20080ENDWHILE0090RETURNcount#0100ENDFUNCfactors#0110//0120ZONE40130seen#:=00140FORi#:=2TO120DO0150IFfactors#(factors#(i#))=1THEN0160PRINTi#,0170seen#:+10180IFseen#MOD18=0THENPRINT0190ENDIF0200ENDFORi#0210PRINT0220END
4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 3233 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 6263 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 9192 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118119 120
(defunattractivep(n)(primep(length(factorsn)))); For primality testing we can use different methods, but since we have to define factors that's what we'll use(defunprimep(n)(=(length(factorsn))1))(defunfactors(n)"Return a list of factors of N."(when(>n1)(loopwithmax-d=(isqrtn)ford=2then(if(evenpd)(+d1)(+d2))do(cond((>dmax-d)(return(listn))); n is prime((zerop(remnd))(return(consd(factors(truncatend)))))))))
(dotimes (i 121) (when (attractivep i) (princ i) (princ " ")))4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
include "cowgol.coh";const MAXIMUM := 120;typedef N is int(0, MAXIMUM + 1);var prime: uint8[MAXIMUM + 1];sub Sieve() is MemSet(&prime[0], 1, @bytesof prime); prime[0] := 0; prime[1] := 0; var cand: N := 2; while cand <= MAXIMUM >> 1 loop if prime[cand] != 0 then var comp := cand + cand; while comp <= MAXIMUM loop prime[comp] := 0; comp := comp + cand; end loop; end if; cand := cand + 1; end loop;end sub;sub Factors(n: N): (count: N) is count := 0; var p: N := 2; while p <= MAXIMUM loop if prime[p] != 0 then while n % p == 0 loop count := count + 1; n := n / p; end loop; end if; p := p + 1; end loop;end sub;sub Padding(n: N) is if n < 10 then print(" "); elseif n < 100 then print(" "); else print(" "); end if;end sub;var cand: N := 2;var col: uint8 := 0;Sieve();while cand <= MAXIMUM loop if prime[Factors(cand)] != 0 then Padding(cand); print_i32(cand as uint32); col := col + 1; if col % 18 == 0 then print_nl(); end if; end if; cand := cand + 1;end loop;print_nl();4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
forx=1to120letn=xletc=0doifint(nmod2)=0thenletn=int(n/2)letc=c+1endifwaitloopint(nmod2)=0fori=3tosqrt(n)step2doifint(nmodi)=0thenletn=int(n/i)letc=c+1endifwaitloopint(nmodi)=0nextiifn>2thenletc=c+1endififprime(c)thenprintx," ",endifnextx
4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
importstd.stdio;enumMAX=120;boolisPrime(intn){if(n<2)returnfalse;if(n%2==0)returnn==2;if(n%3==0)returnn==3;intd=5;while(d*d<=n){if(n%d==0)returnfalse;d+=2;if(n%d==0)returnfalse;d+=4;}returntrue;}intprimeFactorCount(intn){if(n==1)return0;if(isPrime(n))return1;intcount;intf=2;while(true){if(n%f==0){count++;n/=f;if(n==1)returncount;if(isPrime(n))f=n;}elseif(f>=3){f+=2;}else{f=3;}}}voidmain(){writeln("The attractive numbers up to and including ",MAX," are:");inti=1;intcount;while(i<=MAX){intn=primeFactorCount(i);if(isPrime(n)){writef("%4d",i);if(++count%20==0)writeln;}++i;}writeln;}
The attractive numbers up to and including 120 are: 4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
See#Pascal.
/* Sieve of Eratosthenes */proc nonrec sieve([*] bool prime) void: word p, c, max; max := (dim(prime,1)-1)>>1; prime[0] := false; prime[1] := false; for p from 2 upto max do prime[p] := true od; for p from 2 upto max>>1 do if prime[p] then for c from p*2 by p upto max do prime[c] := false od fi odcorp/* Count the prime factors of a number */proc nonrec n_factors(word n; [*] bool prime) word: word count, fac; fac := 2; count := 0; while fac <= n do if prime[fac] then while n % fac = 0 do count := count + 1; n := n / fac od fi; fac := fac + 1 od; countcorp/* Find attractive numbers <= 120 */proc nonrec main() void: word MAX = 120; [MAX+1] bool prime; unsigned MAX i; byte col; sieve(prime); col := 0; for i from 2 upto MAX do if prime[n_factors(i, prime)] then write(i:4); col := col + 1; if col % 18 = 0 then writeln() fi fi odcorp
4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
func isprim num . if num < 2 return 0 . i = 2 while i <= sqrt num if num mod i = 0 return 0 . i += 1 . return 1.func count n . f = 2 repeat if n mod f = 0 cnt += 1 n /= f else f += 1 . until n = 1 . return cnt.for i = 2 to 120 n = count i if isprim n = 1 write i & " " ..
// attractive_numbers.fsx// taken from Primality by trial divisionletrecprimes=letnext_states=Some(s,s+2)Seq.cache(Seq.append(seq[2;3;5])(Seq.unfoldnext_state7|>Seq.filteris_prime))andis_primenumber=letrecis_prime_corenumbercurrentlimit=letcprime=primes|>Seq.itemcurrentifcprime>=limitthentrueelifnumber%cprime=0thenfalseelseis_prime_corenumber(current+1)(number/cprime)ifnumber=2thentrueelifnumber<2thenfalseelseis_prime_corenumber0number// taken from Prime decomposition task and modified to addletcount_prime_divisorsn=letrecloopcncount=letp=Seq.itemnprimesifc<(p*p)thencountelifc%p=0thenloop(c/p)n(count+1)elseloopc(n+1)countloopn01letis_attractive=count_prime_divisors>>is_primeletprint_iterin=ifi%10=9thenprintfn"%d"nelseprintf"%d\t"n[1..120]|>List.filteris_attractive|>List.iteriprint_iter
>dotnet fsi attractive_numbers.fsx4 6 8 9 10 12 14 15 18 2021 22 25 26 27 28 30 32 33 3435 38 39 42 44 45 46 48 49 5051 52 55 57 58 62 63 65 66 6869 70 72 74 75 76 77 78 80 8285 86 87 91 92 93 94 95 98 99102 105 106 108 110 111 112 114 115 116117 118 119 120 %
USING:formattinggroupingiomath.primesmath.primes.factorsmath.rangessequences;"The attractive numbers up to and including 120 are:"print120[1,b][factorslengthprime?]filter20<groups>[["%4d"printf]eachnl]each
The attractive numbers up to and including 120 are: 4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
programattractive_numbersuseiso_fortran_env,only:output_unitimplicit noneinteger,parameter::maximum=120,line_break=20integer::i,counterwrite(output_unit,'(A,x,I0,x,A)')"The attractive numbers up to and including",maximum,"are:"counter=0doi=1,maximumif(is_prime(count_prime_factors(i)))then write(output_unit,'(I0,x)',advance="no")icounter=counter+1if(modulo(counter,line_break)==0)write(output_unit,*)end if end do write(output_unit,*)contains pure functionis_prime(n)integer,intent(in)::nlogical::is_primeinteger::dis_prime=.false.d=5if(n<2)return if(modulo(n,2)==0)thenis_prime=n==2return end if if(modulo(n,3)==0)thenis_prime=n==3return end if do if(d**2>n)thenis_prime=.true.return end if if(modulo(n,d)==0)thenis_prime=.false.return end ifd=d+2if(modulo(n,d)==0)thenis_prime=.false.return end ifd=d+4end dois_prime=.true.end functionis_primepure functioncount_prime_factors(n)integer,intent(in)::ninteger::count_prime_factorsinteger::i,fcount_prime_factors=0if(n==1)return if(is_prime(n))thencount_prime_factors=1return end ifcount_prime_factors=0f=2i=ndo if(modulo(i,f)==0)thencount_prime_factors=count_prime_factors+1i=i/fif(i==1)exit if(is_prime(i))f=ielse if(f>=3)thenf=f+2elsef=3end if end do end functioncount_prime_factorsend programattractive_numbers
The attractive numbers up to and including 120 are:4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
Constlimite=120DeclareFunctionesPrimo(nAsInteger)AsBooleanDeclareFunctionContandoFactoresPrimos(nAsInteger)AsIntegerFunctionesPrimo(nAsInteger)AsBooleanIfn<2ThenReturnfalseIfnMod2=0ThenReturnn=2IfnMod3=0ThenReturnn=3DimAsIntegerd=5Whiled*d<=nIfnModd=0ThenReturnfalsed+=2IfnModd=0ThenReturnfalsed+=4WendReturntrueEndFunctionFunctionContandoFactoresPrimos(nAsInteger)AsIntegerIfn=1ThenReturnfalseIfesPrimo(n)ThenReturntrueDimAsIntegerf=2,contar=0WhiletrueIfnModf=0Thencontar+=1n=n/fIfn=1ThenReturncontarIfesPrimo(n)Thenf=nElseiff>=3Thenf+=2Elsef=3EndIfWendEndFunction' Mostrar la sucencia de números atractivos hasta 120.DimAsIntegeri=1,longlinea=0Print"Los numeros atractivos hasta e incluyendo";limite;" son: "Whilei<=limiteDimAsIntegern=ContandoFactoresPrimos(i)IfesPrimo(n)ThenPrintUsing"####";i;longlinea+=1:IflonglineaMod20=0ThenPrint""EndIfi+=1WendEnd
Los numeros atractivos hasta e incluyendo 120 son: 4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
println[select[2 to 120, {|x| !isPrime[x] and isPrime[length[factorFlat[x]]]}]][4, 6, 8, 9, 10, 12, 14, 15, 18, 20, 21, 22, 25, 26, 27, 28, 30, 32, 33, 34, 35, 38, 39, 42, 44, 45, 46, 48, 49, 50, 51, 52, 55, 57, 58, 62, 63, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 82, 85, 86, 87, 91, 92, 93, 94, 95, 98, 99, 102, 105, 106, 108, 110, 111, 112, 114, 115, 116, 117, 118, 119, 120]
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for storage and transfer purposes more than visualization and edition.
Programs in Fōrmulæ are created/edited online in itswebsite.
Inthis page you can see and run the program(s) related to this task and their results. You can also change either the programs or the parameters they are called with, for experimentation, but remember that these programs were created with the main purpose of showing a clear solution of the task, and they generally lack any kind of validation.
Solution. Let us make a function to determine whether a number is "attractive" or not.
Test case. Show sequence items up to 120.
local fn IsPrime( n as NSUInteger ) as BOOL NSUInteger i if ( n < 2 ) then exit fn = NO if ( n = 2 ) then exit fn = YES if ( n mod 2 == 0 ) then exit fn = NO for i = 3 to int(n^.5) step 2 if ( n mod i == 0 ) then exit fn = NO nextend fn = YESlocal fn Factors( n as NSInteger ) as NSInteger NSInteger count = 0, f = 2 do if n mod f == 0 then count++ : n /= f else f++ until ( f > n )end fn = countvoid local fn AttractiveNumbers( limit as NSInteger ) NSInteger c = 0, n printf @"Attractive numbers through %d are:", limit for n = 4 to limit if fn IsPrime( fn Factors( n ) ) printf @"%4d \b", n c++ if ( c mod 10 == 0 ) then print end if nextend fnfn AttractiveNumbers( 120 )HandleEvents
Attractive numbers through 120 are: 4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
Simple functions to test for primality and to count prime factors suffice here.
packagemainimport"fmt"funcisPrime(nint)bool{switch{casen<2:returnfalsecasen%2==0:returnn==2casen%3==0:returnn==3default:d:=5ford*d<=n{ifn%d==0{returnfalse}d+=2ifn%d==0{returnfalse}d+=4}returntrue}}funccountPrimeFactors(nint)int{switch{casen==1:return0caseisPrime(n):return1default:count,f:=0,2for{ifn%f==0{count++n/=fifn==1{returncount}ifisPrime(n){f=n}}elseiff>=3{f+=2}else{f=3}}returncount}}funcmain(){constmax=120fmt.Println("The attractive numbers up to and including",max,"are:")count:=0fori:=1;i<=max;i++{n:=countPrimeFactors(i)ifisPrime(n){fmt.Printf("%4d",i)count++ifcount%20==0{fmt.Println()}}}fmt.Println()}
The attractive numbers up to and including 120 are: 4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
classAttractiveNumbers{staticbooleanisPrime(intn){if(n<2)returnfalseif(n%2==0)returnn==2if(n%3==0)returnn==3intd=5while(d*d<=n){if(n%d==0)returnfalsed+=2if(n%d==0)returnfalsed+=4}returntrue}staticintcountPrimeFactors(intn){if(n==1)return0if(isPrime(n))return1intcount=0,f=2while(true){if(n%f==0){count++n/=fif(n==1)returncountif(isPrime(n))f=n}elseif(f>=3)f+=2elsef=3}}staticvoidmain(String[]args){finalintmax=120printf("The attractive numbers up to and including %d are:\n",max)intcount=0for(inti=1;i<=max;++i){intn=countPrimeFactors(i)if(isPrime(n)){printf("%4d",i)if(++count%20==0)println()}}println()}}
The attractive numbers up to and including 120 are: 4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
importData.Numbers.PrimesimportData.Bool(bool)attractiveNumbers::[Integer]attractiveNumbers=[1..]>>=(bool[].return)<*>(isPrime.length.primeFactors)main::IO()main=print$takeWhile(<=120)attractiveNumbers
Or equivalently, as a list comprehension:
importData.Numbers.PrimesattractiveNumbers::[Integer]attractiveNumbers=[x|x<-[1..],isPrime(length(primeFactorsx))]main::IO()main=print$takeWhile(<=120)attractiveNumbers
Or simply:
importData.Numbers.PrimesattractiveNumbers::[Integer]attractiveNumbers=filter(isPrime.length.primeFactors)[1..]main::IO()main=print$takeWhile(<=120)attractiveNumbers
[4,6,8,9,10,12,14,15,18,20,21,22,25,26,27,28,30,32,33,34,35,38,39,42,44,45,46,48,49,50,51,52,55,57,58,62,63,65,66,68,69,70,72,74,75,76,77,78,80,82,85,86,87,91,92,93,94,95,98,99,102,105,106,108,110,111,112,114,115,116,117,118,119,120]
Notice that this implementation is not optimally performant, as primes is called multiple times when the output could be shared, the same is true for distinct-factor and factor.
(function primes n (let find-range (range 2 (inc n)) check-nums (range 2 (-> n ceil sqrt inc)) skip-each-after #(skip-each % (skip %1 %2)) muls (xmap #(drop 0 (skip-each-after (dec %1) % find-range)) check-nums)) (remove (flatten muls) find-range))(function distinct-factor n (filter @(div? n) (primes n)))(function factor n (map (fn t (find (div? n) (map @(** t) (range (round (sqrt n)) 0)))) (distinct-factor n)))(function decomposed-factors n (map (fn dist t (repeat dist (/ (logn t) (logn dist)))) (distinct-factor n) (factor n)))(var prime? @((primes %)))(var attract-num? (comp decomposed-factors flatten len prime?))(filter attract-num? (range 121))
echo(#~(1p:])@#@q:)>:i.120
4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
(()=>{'use strict';// attractiveNumbers :: () -> Gen [Int]constattractiveNumbers=()=>// An infinite series of attractive numbers.filter(compose(isPrime,length,primeFactors))(enumFrom(1));// ----------------------- TEST -----------------------// main :: IO ()constmain=()=>showCols(10)(takeWhile(ge(120))(attractiveNumbers()));// ---------------------- PRIMES ----------------------// isPrime :: Int -> BoolconstisPrime=n=>{// True if n is prime.if(2===n||3===n){returntrue}if(2>n||0===n%2){returnfalse}if(9>n){returntrue}if(0===n%3){returnfalse}return!enumFromThenTo(5)(11)(1+Math.floor(Math.pow(n,0.5))).some(x=>0===n%x||0===n%(2+x));};// primeFactors :: Int -> [Int]constprimeFactors=n=>{// A list of the prime factors of n.constgo=x=>{constroot=Math.floor(Math.sqrt(x)),m=until(([q,_])=>(root<q)||(0===(x%q)))(([_,r])=>[step(r),1+r])([0===x%2?(2):3,1])[0];returnm>root?([x]):([m].concat(go(Math.floor(x/m))));},step=x=>1+(x<<2)-((x>>1)<<1);returngo(n);};// ---------------- GENERIC FUNCTIONS -----------------// chunksOf :: Int -> [a] -> [[a]]constchunksOf=n=>xs=>enumFromThenTo(0)(n)(xs.length-1).reduce((a,i)=>a.concat([xs.slice(i,(n+i))]),[]);// compose (<<<) :: (b -> c) -> (a -> b) -> a -> cconstcompose=(...fs)=>fs.reduce((f,g)=>x=>f(g(x)),x=>x);// enumFrom :: Enum a => a -> [a]function*enumFrom(x){// A non-finite succession of enumerable// values, starting with the value x.letv=x;while(true){yieldv;v=1+v;}}// enumFromThenTo :: Int -> Int -> Int -> [Int]constenumFromThenTo=x1=>x2=>y=>{constd=x2-x1;returnArray.from({length:Math.floor(y-x2)/d+2},(_,i)=>x1+(d*i));};// filter :: (a -> Bool) -> Gen [a] -> [a]constfilter=p=>xs=>{function*go(){letx=xs.next();while(!x.done){letv=x.value;if(p(v)){yieldv}x=xs.next();}}returngo(xs);};// ge :: Ord a => a -> a -> Boolconstge=x=>// True if x >= yy=>x>=y;// justifyRight :: Int -> Char -> String -> StringconstjustifyRight=n=>// The string s, preceded by enough padding (with// the character c) to reach the string length n.c=>s=>n>s.length?(s.padStart(n,c)):s;// last :: [a] -> aconstlast=xs=>// The last item of a list.0<xs.length?xs.slice(-1)[0]:undefined;// length :: [a] -> Intconstlength=xs=>// Returns Infinity over objects without finite// length. This enables zip and zipWith to choose// the shorter argument when one is non-finite,// like cycle, repeat etc(Array.isArray(xs)||'string'===typeofxs)?(xs.length):Infinity;// map :: (a -> b) -> [a] -> [b]constmap=f=>// The list obtained by applying f// to each element of xs.// (The image of xs under f).xs=>(Array.isArray(xs)?(xs):xs.split('')).map(f);// showCols :: Int -> [a] -> StringconstshowCols=w=>xs=>{constys=xs.map(str),mx=last(ys).length;returnunlines(chunksOf(w)(ys).map(row=>row.map(justifyRight(mx)(' ')).join(' ')))};// str :: a -> Stringconststr=x=>x.toString();// takeWhile :: (a -> Bool) -> Gen [a] -> [a]consttakeWhile=p=>xs=>{constys=[];letnxt=xs.next(),v=nxt.value;while(!nxt.done&&p(v)){ys.push(v);nxt=xs.next();v=nxt.value}returnys;};// unlines :: [String] -> Stringconstunlines=xs=>// A single string formed by the intercalation// of a list of strings with the newline character.xs.join('\n');// until :: (a -> Bool) -> (a -> a) -> a -> aconstuntil=p=>f=>x=>{letv=x;while(!p(v))v=f(v);returnv;};// MAIN ---returnmain();})();
4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99102 105 106 108 110 111 112 114 115 116117 118 119 120
publicclassAttractive{staticbooleanis_prime(intn){if(n<2)returnfalse;if(n%2==0)returnn==2;if(n%3==0)returnn==3;intd=5;while(d*d<=n){if(n%d==0)returnfalse;d+=2;if(n%d==0)returnfalse;d+=4;}returntrue;}staticintcount_prime_factors(intn){if(n==1)return0;if(is_prime(n))return1;intcount=0,f=2;while(true){if(n%f==0){count++;n/=f;if(n==1)returncount;if(is_prime(n))f=n;}elseif(f>=3)f+=2;elsef=3;}}publicstaticvoidmain(String[]args){finalintmax=120;System.out.printf("The attractive numbers up to and including %d are:\n",max);for(inti=1,count=0;i<=max;++i){intn=count_prime_factors(i);if(is_prime(n)){System.out.printf("%4d",i);if(++count%20==0)System.out.println();}}System.out.println();}}
The attractive numbers up to and including 120 are: 4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
Works with gojq, the Go implementation of jq
This entry uses:
def count(s): reduce s as $x (null; .+1);def is_attractive: count(prime_factors) | is_prime;def printattractive($m; $n): "The attractive numbers from \($m) to \($n) are:\n", [range($m; $n+1) | select(is_attractive)]; printattractive(1; 120)
The attractive numbers from 1 to 120 are:[4,6,8,9,10,12,14,15,18,20,21,22,25,26,27,28,30,32,33,34,35,38,39,42,44,45,46,48,49,50,51,52,55,57,58,62,63,65,66,68,69,70,72,74,75,76,77,78,80,82,85,86,87,91,92,93,94,95,98,99,102,105,106,108,110,111,112,114,115,116,117,118,119,120]
usingPrimes# oneliner is println("The attractive numbers from 1 to 120 are:\n", filter(x -> isprime(sum(values(factor(x)))), 1:120))isattractive(n)=isprime(sum(values(factor(n))))printattractive(m,n)=println("The attractive numbers from$m to$n are:\n",filter(isattractive,m:n))printattractive(1,120)
The attractive numbers from 1 to 120 are:[4, 6, 8, 9, 10, 12, 14, 15, 18, 20, 21, 22, 25, 26, 27, 28, 30, 32, 33, 34, 35, 38, 39, 42, 44, 45, 46, 48, 49, 50, 51, 52, 55, 57, 58, 62, 63, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 82, 85, 86, 87, 91, 92, 93, 94, 95, 98, 99, 102, 105, 106, 108, 110, 111, 112, 114, 115, 116, 117, 118, 119, 120]
// Version 1.3.21constvalMAX=120funisPrime(n:Int):Boolean{if(n<2)returnfalseif(n%2==0)returnn==2if(n%3==0)returnn==3vard:Int=5while(d*d<=n){if(n%d==0)returnfalsed+=2if(n%d==0)returnfalsed+=4}returntrue}funcountPrimeFactors(n:Int)=when{n==1->0isPrime(n)->1else->{varnn=nvarcount=0varf=2while(true){if(nn%f==0){count++nn/=fif(nn==1)breakif(isPrime(nn))f=nn}elseif(f>=3){f+=2}else{f=3}}count}}funmain(){println("The attractive numbers up to and including $MAX are:")varcount=0for(iin1..MAX){valn=countPrimeFactors(i)if(isPrime(n)){System.out.printf("%4d",i)if(++count%20==0)println()}}println()}
The attractive numbers up to and including 120 are: 4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
; This is not strictly LLVM, as it uses the C library function "printf".; LLVM does not provide a way to print values, so the alternative would be; to just load the string into memory, and that would be boring.$"ATTRACTIVE_STR"=comdatany$"FORMAT_NUMBER"=comdatany$"NEWLINE_STR"=comdatany@"ATTRACTIVE_STR"=linkonce_odrunnamed_addrconstant[52xi8]c"The attractive numbers up to and including %d are:\0A\00",comdat,align1@"FORMAT_NUMBER"=linkonce_odrunnamed_addrconstant[4xi8]c"%4d\00",comdat,align1@"NEWLINE_STR"=linkonce_odrunnamed_addrconstant[2xi8]c"\0A\00",comdat,align1;--- The declaration for the external C printf function.declarei32@printf(i8*,...); Function Attrs: noinline nounwind optnone uwtabledefinezeroexti1@is_prime(i32)#0{%2=allocai1,align1;-- allocate return value%3=allocai32,align4;-- allocate n%4=allocai32,align4;-- allocate dstorei32%0,i32*%3,align4;-- store local copy of nstorei325,i32*%4,align4;-- store 5 in d%5=loadi32,i32*%3,align4;-- load n%6=icmpslti32%5,2;-- n < 2bri1%6,label%nlt2,label%nisevennlt2:storei1false,i1*%2,align1;-- store false in return valuebrlabel%exitniseven:%7=loadi32,i32*%3,align4;-- load n%8=sremi32%7,2;-- n % 2%9=icmpnei32%8,0;-- (n % 2) != 0bri1%9,label%odd,label%eveneven:%10=loadi32,i32*%3,align4;-- load n%11=icmpeqi32%10,2;-- n == 2storei1%11,i1*%2,align1;-- store (n == 2) in return valuebrlabel%exitodd:%12=loadi32,i32*%3,align4;-- load n%13=sremi32%12,3;-- n % 3%14=icmpnei32%13,0;-- (n % 3) != 0bri1%14,label%loop,label%div3div3:%15=loadi32,i32*%3,align4;-- load n%16=icmpeqi32%15,3;-- n == 3storei1%16,i1*%2,align1;-- store (n == 3) in return valuebrlabel%exitloop:%17=loadi32,i32*%4,align4;-- load d%18=loadi32,i32*%4,align4;-- load d%19=mulnswi32%17,%18;-- d * d%20=loadi32,i32*%3,align4;-- load n%21=icmpslei32%19,%20;-- (d * d) <= nbri1%21,label%first,label%primefirst:%22=loadi32,i32*%3,align4;-- load n%23=loadi32,i32*%4,align4;-- load d%24=sremi32%22,%23;-- n % d%25=icmpnei32%24,0;-- (n % d) != 0bri1%25,label%second,label%notprimesecond:%26=loadi32,i32*%4,align4;-- load d%27=addnswi32%26,2;-- increment d by 2storei32%27,i32*%4,align4;-- store d%28=loadi32,i32*%3,align4;-- load n%29=loadi32,i32*%4,align4;-- load d%30=sremi32%28,%29;-- n % d%31=icmpnei32%30,0;-- (n % d) != 0bri1%31,label%loop_end,label%notprimeloop_end:%32=loadi32,i32*%4,align4;-- load d%33=addnswi32%32,4;-- increment d by 4storei32%33,i32*%4,align4;-- store dbrlabel%loopnotprime:storei1false,i1*%2,align1;-- store false in return valuebrlabel%exitprime:storei1true,i1*%2,align1;-- store true in return valuebrlabel%exitexit:%34=loadi1,i1*%2,align1;-- load return valuereti1%34}; Function Attrs: noinline nounwind optnone uwtabledefinei32@count_prime_factors(i32)#0{%2=allocai32,align4;-- allocate return value%3=allocai32,align4;-- allocate n%4=allocai32,align4;-- allocate count%5=allocai32,align4;-- allocate fstorei32%0,i32*%3,align4;-- store local copy of nstorei320,i32*%4,align4;-- store zero in countstorei322,i32*%5,align4;-- store 2 in f%6=loadi32,i32*%3,align4;-- load n%7=icmpeqi32%6,1;-- n == 1bri1%7,label%eq1,label%ne1eq1:storei320,i32*%2,align4;-- store zero in return valuebrlabel%exitne1:%8=loadi32,i32*%3,align4;-- load n%9=callzeroexti1@is_prime(i32%8);-- is n prime?bri1%9,label%prime,label%loopprime:storei321,i32*%2,align4;-- store a in return valuebrlabel%exitloop:%10=loadi32,i32*%3,align4;-- load n%11=loadi32,i32*%5,align4;-- load f%12=sremi32%10,%11;-- n % f%13=icmpnei32%12,0;-- (n % f) != 0bri1%13,label%br2,label%br1br1:%14=loadi32,i32*%4,align4;-- load count%15=addnswi32%14,1;-- increment countstorei32%15,i32*%4,align4;-- store count%16=loadi32,i32*%5,align4;-- load f%17=loadi32,i32*%3,align4;-- load n%18=sdivi32%17,%16;-- n / fstorei32%18,i32*%3,align4;-- n = n / f%19=loadi32,i32*%3,align4;-- load n%20=icmpeqi32%19,1;-- n == 1bri1%20,label%br1_1,label%br1_2br1_1:%21=loadi32,i32*%4,align4;-- load countstorei32%21,i32*%2,align4;-- store the count in the return valuebrlabel%exitbr1_2:%22=loadi32,i32*%3,align4;-- load n%23=callzeroexti1@is_prime(i32%22);-- is n prime?bri1%23,label%br1_3,label%loopbr1_3:%24=loadi32,i32*%3,align4;-- load nstorei32%24,i32*%5,align4;-- f = nbrlabel%loopbr2:%25=loadi32,i32*%5,align4;-- load f%26=icmpsgei32%25,3;-- f >= 3bri1%26,label%br2_1,label%br3br2_1:%27=loadi32,i32*%5,align4;-- load f%28=addnswi32%27,2;-- increment f by 2storei32%28,i32*%5,align4;-- store fbrlabel%loopbr3:storei323,i32*%5,align4;-- store 3 in fbrlabel%loopexit:%29=loadi32,i32*%2,align4;-- load return valuereti32%29}; Function Attrs: noinline nounwind optnone uwtabledefinei32@main()#0{%1=allocai32,align4;-- allocate i%2=allocai32,align4;-- allocate n%3=allocai32,align4;-- countstorei320,i32*%3,align4;-- store zero in count%4=calli32(i8*,...)@printf(i8*getelementptrinbounds([52xi8],[52xi8]*@"ATTRACTIVE_STR",i320,i320),i32120)storei321,i32*%1,align4;-- store 1 in ibrlabel%looploop:%5=loadi32,i32*%1,align4;-- load i%6=icmpslei32%5,120;-- i <= 120bri1%6,label%loop_body,label%exitloop_body:%7=loadi32,i32*%1,align4;-- load i%8=calli32@count_prime_factors(i32%7);-- count factors of istorei32%8,i32*%2,align4;-- store factors in n%9=callzeroexti1@is_prime(i32%8);-- is n prime?bri1%9,label%prime_branch,label%loop_incprime_branch:%10=loadi32,i32*%1,align4;-- load i%11=calli32(i8*,...)@printf(i8*getelementptrinbounds([4xi8],[4xi8]*@"FORMAT_NUMBER",i320,i320),i32%10)%12=loadi32,i32*%3,align4;-- load count%13=addnswi32%12,1;-- increment countstorei32%13,i32*%3,align4;-- store count%14=sremi32%13,20;-- count % 20%15=icmpnei32%14,0;-- (count % 20) != 0bri1%15,label%loop_inc,label%row_endrow_end:%16=calli32(i8*,...)@printf(i8*getelementptrinbounds([2xi8],[2xi8]*@"NEWLINE_STR",i320,i320))brlabel%loop_incloop_inc:%17=loadi32,i32*%1,align4;-- load i%18=addnswi32%17,1;-- increment istorei32%18,i32*%1,align4;-- store ibrlabel%loopexit:%19=calli32(i8*,...)@printf(i8*getelementptrinbounds([2xi8],[2xi8]*@"NEWLINE_STR",i320,i320))reti320}attributes#0={noinlinenounwindoptnoneuwtable"correctly-rounded-divide-sqrt-fp-math"="false""disable-tail-calls"="false""less-precise-fpmad"="false""no-frame-pointer-elim"="false""no-infs-fp-math"="false""no-jump-tables"="false""no-nans-fp-math"="false""no-signed-zeros-fp-math"="false""no-trapping-math"="false""stack-protector-buffer-size"="8""target-cpu"="x86-64""target-features"="+fxsr,+mmx,+sse,+sse2,+x87""unsafe-fp-math"="false""use-soft-float"="false"}
The attractive numbers up to and including 120 are: 4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
-- Returns true if x is prime, and false otherwisefunctionisPrime(x)ifx<2thenreturnfalseendifx<4thenreturntrueendifx%2==0thenreturnfalseendford=3,math.sqrt(x),2doifx%d==0thenreturnfalseendendreturntrueend-- Compute the prime factors of nfunctionfactors(n)localfacList,divisor,count={},1ifn<2thenreturnfacListendwhilenotisPrime(n)dowhilenotisPrime(divisor)dodivisor=divisor+1endcount=0whilen%divisor==0don=n/divisortable.insert(facList,divisor)enddivisor=divisor+1ifn==1thenreturnfacListendendtable.insert(facList,n)returnfacListend-- Main procedurefori=1,120doifisPrime(#factors(i))thenio.write(i.."\t")endend
4 6 8 9 10 12 14 15 18 20 21 22 25 26 2728 30 32 33 34 35 38 39 42 44 45 46 48 49 5051 52 55 57 58 62 63 65 66 68 69 70 72 74 7576 77 78 80 82 85 86 87 91 92 93 94 95 98 99102 105 106 108 110 111 112 114 115 116 117 118 119 120
attractivenumbers := proc(n::posint)local an, i;an :=[]:for i from 1 to n do if isprime(NumberTheory:-NumberOfPrimeFactors(i)) then an := [op(an), i]: end if:end do:end proc:attractivenumbers(120);
[4, 6, 8, 9, 10, 12, 14, 15, 18, 20, 21, 22, 25, 26, 27, 28, 30, 32, 33, 34, 35, 38, 39, 42, 44, 45, 46, 48, 49, 50, 51, 52, 55, 57, 58, 62, 63, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 82, 85, 86, 87, 91, 92, 93, 94, 95, 98, 99, 102, 105, 106, 108, 110, 111, 112, 114, 115, 116, 117, 118, 119, 120]
ClearAll[AttractiveNumberQ]AttractiveNumberQ[n_Integer]:=FactorInteger[n][[All,2]]//Total//PrimeQReap[Do[If[AttractiveNumberQ[i],Sow[i]],{i,120}]][[2,1]]
{4,6,8,9,10,12,14,15,18,20,21,22,25,26,27,28,30,32,33,34,35,38,39,42,44,45,46,48,49,50,51,52,55,57,58,62,63,65,66,68,69,70,72,74,75,76,77,78,80,82,85,86,87,91,92,93,94,95,98,99,102,105,106,108,110,111,112,114,115,116,117,118,119,120}AttractiveNumber(N):=block([Q:0],ifnotprimep(N)then(ifprimep(apply("+",map(lambda([Z],Z[2]),ifactors(N))))thenQ:N),Q)$delete(0,makelist(AttractiveNumber(K),K,1,120));
Using sublist
attractivep(n):=block(ifactors(n),apply("+",map(second,%%)),ifprimep(%%)thentrue)$sublist(makelist(i,i,120),attractivep);
[4,6,8,9,10,12,14,15,18,20,21,22,25,26,27,28,30,32,33,34,35,38,39,42,44,45,46,48,49,50,51,52,55,57,58,62,63,65,66,68,69,70,72,74,75,76,77,78,80,82,85,86,87,91,92,93,94,95,98,99,102,105,106,108,110,111,112,114,115,116,117,118,119,120]
isPrime=function(n)ifn<2thenreturnfalseifn<4thenreturntrueforiinrange(2,floor(n^0.5))ifn%i==0thenreturnfalseendforreturntrueendfunctioncountFactors=function(n)cnt=0foriinrange(2,n)whilen%i==0cnt+=1n/=iendwhileendforreturncntendfunctionisAttractive=function(n)ifn<1thenreturnfalsefactorCnt=countFactors(n)returnisPrime(factorCnt)endfunctionnumbers=[]foriinrange(2,120)ifisAttractive(i)thennumbers.push(i)endforprintnumbers.join(", ")
4, 6, 8, 9, 10, 12, 14, 15, 18, 20, 21, 22, 25, 26, 27, 28, 30, 32, 33, 34, 35, 38, 39, 42, 44, 45, 46, 48, 49, 50, 51, 52, 55, 57, 58, 62, 63, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 82, 85, 86, 87, 91, 92, 93, 94, 95, 98, 99, 102, 105, 106, 108, 110, 111, 112, 114, 115, 116, 117, 118, 119, 120
main :: [sys_message]main = [Stdout (show (filter attractive [1..120]))]attractive :: num->boolattractive n = #factors (#factors n) = 1factors :: num->[num]factors = f 2 where f d n = [], if d>n = d:f d (n div d), if n mod d=0 = f (d+1) n, otherwise
[4,6,8,9,10,12,14,15,18,20,21,22,25,26,27,28,30,32,33,34,35,38,39,42,44,45,46,48,49,50,51,52,55,57,58,62,63,65,66,68,69,70,72,74,75,76,77,78,80,82,85,86,87,91,92,93,94,95,98,99,102,105,106,108,110,111,112,114,115,116,117,118,119,120]
MODULEAttractiveNumbers;FROMInOutIMPORTWriteCard,WriteLn;CONSTMax=120;VARn,col:CARDINAL;Prime:ARRAY[1..Max]OFBOOLEAN;PROCEDURESieve;VARi,j:CARDINAL;BEGINPrime[1]:=FALSE;FORi:=2TOMaxDOPrime[i]:=TRUE;END;FORi:=2TOMaxDIV2DOIFPrime[i]THENj:=i*2;WHILEj<=MaxDOPrime[j]:=FALSE;j:=j+i;END;END;END;ENDSieve;PROCEDUREFactors(n:CARDINAL):CARDINAL;VARi,factors:CARDINAL;BEGINfactors:=0;FORi:=2TOMaxDOIFi>nTHENRETURNfactors;END;IFPrime[i]THENWHILEnMODi=0DOn:=nDIVi;factors:=factors+1;END;END;END;RETURNfactors;ENDFactors;BEGINSieve();col:=0;FORn:=2TOMaxDOIFPrime[Factors(n)]THENWriteCard(n,4);col:=col+1;IFcolMOD15=0THENWriteLn();END;END;END;WriteLn();ENDAttractiveNumbers.
4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
MAX = 120def is_prime(n)d = 5if (n < 2)return falseendif (n % 2) = 0return n = 2endif (n % 3) = 0return n = 3endwhile (d * d) <= nif n % d = 0return falseendd += 2if n % d = 0return falseendd += 4endreturn trueenddef count_prime_factors(n)count = 0; f = 2if n = 1return 0endif is_prime(n)return 1endwhile trueif (n % f) = 0count += 1n /= fif n = 1return countendif is_prime(n)f = nendelse if f >= 3f += 2elsef = 3endendendi = 0; n = 0; count = 0println format("The attractive numbers up to and including %d are:\n", MAX)for i in range(1, MAX)n = count_prime_factors(i)if is_prime(n)print format("%4d", i)count += 1if (count % 20) = 0printlnendendendprintlnThe attractive numbers up to and including 120 are: 4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
Thefactor function returns a list of the prime factors of an integer with repetition,e. g. (factor 12) is (2 2 3).
(define(prime?n)(=(length(factorn))1))(define(attractive?n)(prime?(length(factorn))));(filterattractive?(sequence2120))
(4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120)
importstrformatconstMAX=120procisPrime(n:int):bool=vard=5ifn<2:returnfalseifnmod2==0:returnn==2ifnmod3==0:returnn==3whiled*d<=n:ifnmodd==0:returnfalseincd,2ifnmodd==0:returnfalseincd,4returntrueproccountPrimeFactors(n_in:int):int=varcount=0varf=2varn=n_inifn==1:return0ifisPrime(n):return1whiletrue:ifnmodf==0:inccountn=ndivfifn==1:returncountifisPrime(n):f=nelif(f>=3):incf,2else:f=3procmain()=varn,count:int=0echofmt"The attractive numbers up to and including {MAX} are:"foriin1..MAX:n=countPrimeFactors(i)ifisPrime(n):write(stdout,fmt"{i:4d}")inccountifcountmod20==0:write(stdout,"\n")write(stdout,"\n")main()
The attractive numbers up to and including 120 are: 4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
class AttractiveNumber { function : Main(args : String[]) ~ Nil { max := 120; "The attractive numbers up to and including {$max} are:"->PrintLine(); count := 0; for(i := 1; i <= max; i += 1;) { n := CountPrimeFactors(i); if(IsPrime(n)) { " {$i}"->Print(); if(++count % 20 = 0) { ""->PrintLine(); }; }; }; ""->PrintLine(); } function : IsPrime(n : Int) ~ Bool { if(n < 2) { return false; }; if(n % 2 = 0) { return n = 2; }; if(n % 3 = 0) { return n = 3; }; d := 5; while(d *d <= n) { if(n % d = 0) { return false; }; d += 2; if(n % d = 0) { return false; }; d += 4; }; return true; } function : CountPrimeFactors(n : Int) ~ Int { if(n = 1) { return 0; }; if(IsPrime(n)) { return 1; }; count := 0; f := 2; while(true) { if(n % f = 0) { count++; n /= f; if(n = 1) { return count; }; if(IsPrime(n)) { f := n; }; } else if(f >= 3) { f += 2; } else { f := 3; }; }; return -1; }}The attractive numbers up to and including 120 are: 4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
packagemainimport"core:fmt"main::proc(){const_max::120fmt.println("\nAttractive numbers up to and including",const_max,"are: ")count:=0foriin1..=const_max{n:=countPrimeFactors(i)ifisPrime(n){fmt.print(i," ")count+=1ifcount%20==0{fmt.println()}}}fmt.println()}/* definitions */isPrime::proc(n:int)->bool{switch{casen<2:returnfalsecasen%2==0:returnn==2casen%3==0:returnn==3case:d:=5ford*d<=n{ifn%d==0{returnfalse}d+=2ifn%d==0{returnfalse}d+=4}returntrue}}countPrimeFactors::proc(n:int)->int{n:=nswitch{casen==1:return0caseisPrime(n):return1case:count,f:=0,2for{ifn%f==0{count+=1n/=fifn==1{returncount}ifisPrime(n){f=n}}elseiff>=3{f+=2}else{f=3}}returncount}}
Attractive numbers up to and including 120 are:4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 3435 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
same procedure as inhttp://rosettacode.org/wiki/Abundant,_deficient_and_perfect_number_classifications
programAttractiveNumbers;{ numbers with count of factors = prime* using modified sieve of erathosthes* by adding the power of the prime to multiples* of the composite number }{$IFDEF FPC}{$MODE DELPHI}{$ELSE}{$APPTYPE CONSOLE}{$ENDIF}usessysutils;//timingconstcTextMany=' with many factors ';cText2=' with only two factors ';cText1=' with only one factor ';typetValue=LongWord;tpValue=^tValue;tPower=array[0..63]oftValue;//2^64varpower:tPower;sieve:arrayofbyte;functionNextPotCnt(p:tValue):tValue;//return the first power <> 0//power == n to base primvari:NativeUint;beginresult:=0;repeati:=power[result];Inc(i);IFi<pthenBREAKelsebegini:=0;power[result]:=0;inc(result);end;untilfalse;power[result]:=i;inc(result);end;procedureInitSieveWith2;//the prime 2, because its the first one, is the one,//which can can be speed up tremendously, by movingvarpSieve:pByte;CopyWidth,lmt:NativeInt;BeginpSieve:=@sieve[0];Lmt:=High(sieve);sieve[1]:=0;sieve[2]:=1;// aka 2^1 -> one factorCopyWidth:=2;whileCopyWidth*2<=LmtdoBegin// copy idx 1,2 to 3,4 | 1..4 to 5..8 | 1..8 to 9..16move(pSieve[1],pSieve[CopyWidth+1],CopyWidth);// 01 -> 0101 -> 01020102-> 0102010301020103inc(CopyWidth,CopyWidth);//*2//increment the factor of last element by one.inc(pSieve[CopyWidth]);//idx 12 1234 12345678//value 01 -> 0102 -> 01020103-> 0102010301020104end;//copy the restmove(pSieve[1],pSieve[CopyWidth+1],Lmt-CopyWidth);//mark 0,1 not prime, 255 factors are today not possible 2^255 >> Uint64sieve[0]:=255;sieve[1]:=255;sieve[2]:=0;// make prime againend;procedureOutCntTime(T:TDateTime;txt:String;cnt:NativeInt);Beginwriteln(cnt:12,txt,T*86400:10:3,' s');end;proceduresievefactors;varT0:TDateTime;pSieve:pByte;i,j,i2,k,lmt,cnt:NativeUInt;BeginInitSieveWith2;pSieve:=@sieve[0];Lmt:=High(sieve);//Divide into 3 section//first i*i*i<= lmt with time expensive NextPotCntT0:=now;cnt:=0;//third root of limit calculate only once, no comparison ala while i*i*i<= lmt dok:=trunc(exp(ln(Lmt)/3));Fori:=3tokdoifpSieve[i]=0thenBegininc(cnt);j:=2*i;fillChar(Power,Sizeof(Power),#0);Power[0]:=1;repeatinc(pSieve[j],NextPotCnt(i));inc(j,i);untilj>lmt;end;OutCntTime(now-T0,cTextMany,cnt);T0:=now;//second i*i <= lmtcnt:=0;i:=k+1;k:=trunc(sqrt(Lmt));Fori:=itokdoifpSieve[i]=0thenBegin//first increment all multiples of prime by oneinc(cnt);j:=2*i;repeatinc(pSieve[j]);inc(j,i);untilj>lmt;//second increment all multiples prime*prime by onei2:=i*i;j:=i2;repeatinc(pSieve[j]);inc(j,i2);untilj>lmt;end;OutCntTime(now-T0,cText2,cnt);T0:=now;//third i*i > lmt -> only one new factorcnt:=0;inc(k);Fori:=ktoLmtshr1doifpSieve[i]=0thenBegininc(cnt);j:=2*i;repeatinc(pSieve[j]);inc(j,i);untilj>lmt;end;OutCntTime(now-T0,cText1,cnt);end;constsmallLmt=120;//needs 1e10 Byte = 10 Gb maybe someone got 128 Gb :-) nearly linear timeBigLimit=10*1000*1000*1000;varT0,T:TDateTime;i,cnt,lmt:NativeInt;Beginsetlength(sieve,smallLmt+1);sievefactors;cnt:=0;Fori:=2tosmallLmtdoBeginifsieve[sieve[i]]=0thenBeginwrite(i:4);inc(cnt);ifcnt>19thenBeginwriteln;cnt:=0;end;end;end;writeln;writeln;T0:=now;setlength(sieve,BigLimit+1);T:=now;writeln('time allocating : ',(T-T0)*86400:8:3,' s');sievefactors;T:=now-T;writeln('time sieving : ',T*86400:8:3,' s');T:=now;cnt:=0;i:=0;lmt:=10;repeatrepeatinc(i);{IF sieve[sieve[i]] = 0 then inc(cnt); takes double time is not relevant}inc(cnt,ORD(sieve[sieve[i]]=0));untili=lmt;writeln(lmt:11,cnt:12);lmt:=10*lmt;untillmt>High(sieve);T:=now-T;writeln('time counting : ',T*86400:8:3,' s');writeln('time total : ',(now-T0)*86400:8:3,' s');end.
1 with many factors 0.000 s 2 with only two factors 0.000 s 13 with only one factor 0.000 s 4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120time allocating : 1.079 s 324 with many factors 106.155 s 9267 with only two factors 33.360 s 234944631 with only one factor 60.264 stime sieving : 200.813 s 10 5 100 60 1000 636 10000 6396 100000 63255 1000000 623232 10000000 6137248 100000000 60472636 1000000000 59640312410000000000 5887824685time counting : 6.130 stime total : 208.022 sreal 3m28,044s
usentheory<is_primefactor>;is_prime+factor$_andprint"$_ "for1..120;
4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
functionattractive(integerlim)sequences={}fori=1tolimdointegern=length(prime_factors(i,true))ifis_prime(n)thens&=iendifendforreturnsendfunctionsequences=attractive(120)printf(1,"There are %d attractive numbers up to and including %d:\n",{length(s),120})pp(s,{pp_IntCh,false})fori=3to6doatomt0=time()integerp=power(10,i),l=length(attractive(p))stringe=elapsed(time()-t0)printf(1,"There are %,d attractive numbers up to %,d (%s)\n",{l,p,e})endfor
There are 74 attractive numbers up to and including 120:{4,6,8,9,10,12,14,15,18,20,21,22,25,26,27,28,30,32,33,34,35,38,39,42,44,45, 46,48,49,50,51,52,55,57,58,62,63,65,66,68,69,70,72,74,75,76,77,78,80,82,85, 86,87,91,92,93,94,95,98,99,102,105,106,108,110,111,112,114,115,116,117,118, 119,120}There are 636 attractive numbers up to 1,000 (0s)There are 6,396 attractive numbers up to 10,000 (0.0s)There are 63,255 attractive numbers up to 100,000 (0.3s)There are 617,552 attractive numbers up to 1,000,000 (4.1s)<?phpfunctionisPrime($x){if($x<2)returnfalse;if($x<4)returntrue;if($x%2==0)returnfalse;for($d=3;$d<sqrt($x);$d++){if($x%$d==0)returnfalse;}returntrue;}functioncountFacs($n){$count=0;$divisor=1;if($n<2)return0;while(!isPrime($n)){while(!isPrime($divisor))$divisor++;while($n%$divisor==0){$n/=$divisor;$count++;}$divisor++;if($n==1)return$count;}return$count+1;}for($i=1;$i<=120;$i++){if(isPrime(countFacs($i)))echo$i." ";}?>
4 6 8 10 12 14 15 18 20 21 22 26 27 28 30 32 33 34 35 36 38 39 42 44 45 46 48 50 51 52 55 57 58 62 63 65 66 68 69 70 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 100 102 105 106 108 110 111 112 114 115 116 117 118 119 120
attractive: procedure options(main); %replace MAX by 120; declare prime(1:MAX) bit(1); sieve: procedure; declare (i, j, sqm) fixed; prime(1) = 0; do i=2 to MAX; prime(i) = '1'b; end; sqm = sqrt(MAX); do i=2 to sqm; if prime(i) then do j=i*2 to MAX by i; prime(j) = '0'b; end; end; end sieve; factors: procedure(nn) returns(fixed); declare (f, i, n, nn) fixed; n = nn; f = 0; do i=2 to n; if prime(i) then do while(mod(n,i) = 0); f = f+1; n = n/i; end; end; return(f); end factors; attractive: procedure(n) returns(bit(1)); declare n fixed; return(prime(factors(n))); end attractive; declare (i, col) fixed; i = 0; col = 0; call sieve(); do i=2 to MAX; if attractive(i) then do; put edit(i) (F(4)); col = col + 1; if mod(col,18) = 0 then put skip; end; end;end attractive;
4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
100H:BDOS: PROCEDURE (F, ARG); DECLARE F BYTE, ARG ADDRESS; GO TO 5; END BDOS;EXIT: PROCEDURE; CALL BDOS(0,0); END EXIT;PUT$CHAR: PROCEDURE (CH); DECLARE CH BYTE; CALL BDOS(2,CH); END PUT$CHAR;DECLARE MAXIMUM LITERALLY '120';PRINT4: PROCEDURE (N); DECLARE (N, MAGN, Z) BYTE; CALL PUT$CHAR(' '); MAGN = 100; Z = 0; DO WHILE MAGN > 0; IF NOT Z AND N < MAGN THEN CALL PUT$CHAR(' '); ELSE DO; CALL PUT$CHAR('0' + N/MAGN); N = N MOD MAGN; Z = 1; END; MAGN = MAGN/10; END;END PRINT4;NEW$LINE: PROCEDURE; CALL PUT$CHAR(13); CALL PUT$CHAR(10);END NEW$LINE;SIEVE: PROCEDURE (MAX, PRIME); DECLARE PRIME ADDRESS; DECLARE (I, J, MAX, P BASED PRIME) BYTE; P(0)=0; P(1)=0; DO I=2 TO MAX; P(I)=1; END; DO I=2 TO SHR(MAX,1); IF P(I) THEN DO J=SHL(I,1) TO MAX BY I; P(J) = 0; END; END;END SIEVE;FACTORS: PROCEDURE (N, MAX, PRIME) BYTE; DECLARE PRIME ADDRESS; DECLARE (I, J, N, MAX, F, P BASED PRIME) BYTE; F = 0; DO I=2 TO MAX; IF P(I) THEN DO WHILE N MOD I = 0; F = F + 1; N = N / I; END; END; RETURN F;END FACTORS;ATTRACTIVE: PROCEDURE(N, MAX, PRIME) BYTE; DECLARE PRIME ADDRESS; DECLARE (N, MAX, P BASED PRIME) BYTE; RETURN P(FACTORS(N, MAX, PRIME));END ATTRACTIVE;DECLARE (I, COL) BYTE INITIAL (0, 0);CALL SIEVE(MAXIMUM, .MEMORY);DO I=2 TO MAXIMUM; IF ATTRACTIVE(I, MAXIMUM, .MEMORY) THEN DO; CALL PRINT4(I); COL = COL + 1; IF COL MOD 18 = 0 THEN CALL NEW$LINE; END;END;CALL EXIT;EOF4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
prime_factors(N,Factors):-Sissqrt(N),prime_factors(N,Factors,S,2).prime_factors(1,[],_,_):-!.prime_factors(N,[P|Factors],S,P):-P=<S,0isNmodP,!,MisN//P,prime_factors(M,Factors,S,P).prime_factors(N,Factors,S,P):-QisP+1,Q=<S,!,prime_factors(N,Factors,S,Q).prime_factors(N,[N],_,_).is_prime(2):-!.is_prime(N):-0isNmod2,!,fail.is_prime(N):-N>2,Sissqrt(N),\+is_composite(N,S,3).is_composite(N,S,P):-P=<S,0isNmodP,!.is_composite(N,S,P):-QisP+2,Q=<S,is_composite(N,S,Q).attractive_number(N):-prime_factors(N,Factors),length(Factors,Len),is_prime(Len).print_attractive_numbers(From,To,_):-From>To,!.print_attractive_numbers(From,To,C):-(attractive_number(From)->writef('%4r',[From]),(0isCmod20->nl;true),C1isC+1;C1=C),NextisFrom+1,print_attractive_numbers(Next,To,C1).main:-print_attractive_numbers(1,120,1).
4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
#MAX=120Dimprime.b(#MAX)FillMemory(@prime(),#MAX,#True,#PB_Byte):FillMemory(@prime(),2,#False,#PB_Byte)Fori=2ToInt(Sqr(#MAX)):n=i*i:Whilen<#MAX:prime(n)=#False:n+i:Wend:NextProcedure.ipfCount(n.i)Sharedprime()Ifn=1:ProcedureReturn0:EndIfIfprime(n):ProcedureReturn1:EndIfcount=0:f=2RepeatIfn%f=0:count+1:n/fIfn=1:ProcedureReturncount:EndIfIfprime(n):f=n:EndIfElseIff>=3:f+2Else:f=3EndIfForEverEndProcedureOpenConsole()PrintN("The attractive numbers up to and including "+Str(#MAX)+" are:")Fori=1To#MAXIfprime(pfCount(i))Print(RSet(Str(i),4)):count+1:Ifcount%20=0:PrintN(""):EndIfEndIfNextPrintN(""):Input()
The attractive numbers up to and including 120 are: 4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
fromsympyimportsieve# library for primesdefget_pfct(n):i=2;factors=[]whilei*i<=n:ifn%i:i+=1else:n//=ifactors.append(i)ifn>1:factors.append(n)returnlen(factors)sieve.extend(110)# first 110 primes...primes=sieve._listpool=[]foreachinxrange(0,121):pool.append(get_pfct(each))fori,eachinenumerate(pool):ifeachinprimes:printi,
4,6,8,9,10,12,14,15,18,20,21,22,25,26,27,28,30,32,33,34,35,38,39,42,44,45,46, 48,49,50,51,52,55,57,58,62,63,65,66,68,69,70,72,74,75,76,77,78,80,82,85,86,87, 91,92,93,94,95,98,99,102,105,106,108,110,111,112,114,115,116,117,118,119,120
Without importing a primes library – at this scale a light and visible implementation is more than enough, and provides more material for comparison.
'''Attractive numbers'''fromitertoolsimportchain,count,takewhilefromfunctoolsimportreduce# attractiveNumbers :: () -> [Int]defattractiveNumbers():'''A non-finite stream of attractive numbers. (OEIS A063989) '''returnfilter(compose(isPrime,len,primeDecomposition),count(1))# TEST ----------------------------------------------------defmain():'''Attractive numbers drawn from the range [1..120]'''forrowinchunksOf(15)(list(takewhile(lambdax:120>=x,attractiveNumbers()))):print(' '.join(map(compose(justifyRight(3)(' '),str),row)))# GENERAL FUNCTIONS ---------------------------------------# chunksOf :: Int -> [a] -> [[a]]defchunksOf(n):'''A series of lists of length n, subdividing the contents of xs. Where the length of xs is not evenly divible, the final list will be shorter than n. '''returnlambdaxs:reduce(lambdaa,i:a+[xs[i:n+i]],range(0,len(xs),n),[])if0<nelse[]# compose :: ((a -> a), ...) -> (a -> a)defcompose(*fs):'''Composition, from right to left, of a series of functions. '''returnlambdax:reduce(lambdaa,f:f(a),fs[::-1],x)# We only need light implementations# of prime functions here:# primeDecomposition :: Int -> [Int]defprimeDecomposition(n):'''List of integers representing the prime decomposition of n. '''defgo(n,p):return[p]+go(n//p,p)if(0==n%p)else[]returnlist(chain.from_iterable(map(lambdap:go(n,p)ifisPrime(p)else[],range(2,1+n))))# isPrime :: Int -> BooldefisPrime(n):'''True if n is prime.'''ifnin(2,3):returnTrueif2>nor0==n%2:returnFalseif9>n:returnTrueif0==n%3:returnFalsereturnnotany(map(lambdax:0==n%xor0==n%(2+x),range(5,1+int(n**0.5),6)))# justifyRight :: Int -> Char -> String -> StringdefjustifyRight(n):'''A string padded at left to length n, using the padding character c. '''returnlambdac:lambdas:s.rjust(n,c)# MAIN ---if__name__=='__main__':main()
4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99102 105 106 108 110 111 112 114 115 116 117 118 119 120
primefactors is defined atPrime decomposition.
[ primefactors size primefactors size 1 = ] is attractive ( n --> b )120 times [ i^ 1+ attractive if [ i^ 1+ echo sp ] ]
4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
is_prime<-function(num){if(num<2)return(FALSE)if(num%%2==0)return(num==2)if(num%%3==0)return(num==3)d<-5while(d*d<=num){if(num%%d==0)return(FALSE)d<-d+2if(num%%d==0)return(FALSE)d<-d+4}TRUE}count_prime_factors<-function(num){if(num==1)return(0)if(is_prime(num))return(1)count<-0f<-2while(TRUE){if(num%%f==0){count<-count+1num<-num/fif(num==1)return(count)if(is_prime(num))f<-num}elseif(f>=3)f<-f+2elsef<-3}}max<-120cat("The attractive numbers up to and including",max,"are:\n")count<-0for(iin1:max){n<-count_prime_factors(i);if(is_prime(n)){cat(i," ",sep="")count<-count+1}}
The attractive numbers up to and including 120 are:4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
#langracket(requiremath/number-theory)(defineattractive?(compose1prime?prime-omega))(filterattractive?(range1121))
(4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120)
(formerly Perl 6)
This algorithm is concise but not really well suited to finding large quantities of consecutive attractive numbers. It works, but isn't especially speedy. More than a hundred thousand or so gets tedious. There are other, much faster (though more verbose) algorithms thatcould be used. This algorithmis well suited to findingarbitrary attractive numbers though.
useLingua::EN::Numbers;usentheory:from<Perl5><factor is_prime>;subdisplay ($n,$m) { ($n..$m).grep: (~*).&factor.elems.&is_prime }subcount ($n,$m) { +($n..$m).grep: (~*).&factor.elems.&is_prime }# The Taskput"Attractive numbers from 1 to 120:\n" ~display(1,120)».fmt("%3d").rotor(20, :partial).join:"\n";# Robusto!for1,1000,1,10000,1,100000,2**73 +1,2**73 +100 ->$a,$b {put"\nCount of attractive numbers from {comma $a} to {comma $b}:\n" ~commacount$a,$b}
Attractive numbers from 1 to 120: 4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99102 105 106 108 110 111 112 114 115 116 117 118 119 120Count of attractive numbers from 1 to 1,000:636Count of attractive numbers from 1 to 10,000:6,396Count of attractive numbers from 1 to 100,000:63,255Count of attractive numbers from 9,444,732,965,739,290,427,393 to 9,444,732,965,739,290,427,492:58
Programming notes: The use of a table that contains some low primes is one fast method to test for primality of the
various prime factors.
The cFact (count factors) function is optimized way beyond what this task requires, and it could be optimized
further by expanding the do whiles clauses (lines 3──►6 in the cFact function).
If the argument for the program is negative, only a count of attractive numbers up to and including │N│ is shown.
/*REXX program finds and shows lists (or counts) attractive numbers up to a specified N.*/parseargN./*get optional argument from the C.L. */ifN==''|N==","thenN=120/*Not specified? Then use the default.*/cnt=N<0/*semaphore used to control the output.*/N=abs(N)/*ensure that N is a positive number.*/callgenP100/*gen 100 primes (high= 541); overkill.*/sw=linesize()-1/*SW: is the usable screen width. */if\cntthensay'attractive numbers up to and including 'commas(N)" are:"#=0/*number of attractive #'s (so far). */$=/*a list of attractive numbers (so far)*/doj=1forN;if@.jtheniterate/*Is it a low prime? Then skip number.*/a=cFact(j)/*call cFact to count the factors in J.*/if\@.atheniterate/*if # of factors not prime, then skip.*/#=#+1/*bump number of attractive #'s found. */ifcnttheniterate/*if not displaying numbers, skip list.*/cj=commas(j);_=$cj/*append a commatized number to $ list.*/iflength(_)>swthendo;saystrip($);$=cj;end/*display a line of numbers.*/else$=_/*append the latest number. */end/*j*/if$\==''&\cntthensaystrip($)/*display any residual numbers in list.*/say;saycommas(#)' attractive numbers found up to and including 'commas(N)exit/*stick a fork in it, we're all done. *//*──────────────────────────────────────────────────────────────────────────────────────*/cFact:procedure;parseargz1oz;ifz<2thenreturnz/*if Z too small, return Z.*/#=0/*#: is the number of factors (so far)*/dowhilez//2==0;#=#+1;z=z%2;end/*maybe add the factor of two. */dowhilez//3==0;#=#+1;z=z%3;end/* " " " " " three.*/dowhilez//5==0;#=#+1;z=z%5;end/* " " " " " five. */dowhilez//7==0;#=#+1;z=z%7;end/* " " " " " seven.*//* [↑] reduce Z by some low primes. */dok=11by6whilek<=z/*insure that K isn't divisible by 3.*/parsevark''-1_/*obtain the last decimal digit of K. */if_\==5thendowhilez//k==0;#=#+1;z=z%k;end/*maybe reduce Z.*/if_==3theniterate/*Next number ÷ by 5? Skip. ____ */ifk*k>ozthenleave/*are we greater than the √ OZ ? */y=k+2/*get next divisor, hopefully a prime.*/dowhilez//y==0;#=#+1;z=z%y;end/*maybe reduce Z.*/end/*k*/ifz\==1thenreturn#+1/*if residual isn't unity, then add one*/return#/*return the number of factors in OZ. *//*──────────────────────────────────────────────────────────────────────────────────────*/commas:parsearg?;dojc=length(?)-3to1by-3;?=insert(',',?,jc);end;return?/*──────────────────────────────────────────────────────────────────────────────────────*/genP:procedureexpose@.;parseargn;@.=0;@.2=1;@.3=1;p=2doj=3by2untilp==n;dok=3by2untilk*k>j;ifj//k==0theniteratejend/*k*/;@.j=1;p=p+1end/*j*/;return/* [↑] generate N primes. */
This REXX program makes use of LINESIZE REXX program (or BIF) which is used to determine the screen width (or linesize) of the terminal (console).
Some REXXes don't have this BIF. It is used here to automatically/idiomatically limit the width of the output list.
The LINESIZE.REX REXX program is included here ───► LINESIZE.REX.
attractive numbers up to and including 120 are:4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 7475 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 12074 attractive numbers found up to and including 120
6,396 attractive numbers found up to and including 10,000
63,255 attractive numbers found up to and including 100,000
623,232 attractive numbers found up to and including 1,000,000
# Project: Attractive Numbersdecomp = []nump = 0see "Attractive Numbers up to 120:" + nlwhile nump < 120decomp = []nump = nump + 1for i = 1 to nump if isPrime(i) and nump%i = 0 add(decomp,i) dec = nump/i while dec%i = 0 add(decomp,i) dec = dec/i end oknextif isPrime(len(decomp)) see string(nump) + " = ["for n = 1 to len(decomp) if n < len(decomp) see string(decomp[n]) + "*" else see string(decomp[n]) + "] - " + len(decomp) + " is prime" + nl oknextokend func 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
Attractive Numbers up to 120:4 = [2*2] - 2 is prime6 = [2*3] - 2 is prime8 = [2*2*2] - 3 is prime9 = [3*3] - 2 is prime10 = [2*5] - 2 is prime12 = [2*2*3] - 3 is prime14 = [2*7] - 2 is prime15 = [3*5] - 2 is prime18 = [2*3*3] - 3 is prime20 = [2*2*5] - 3 is prime.........102 = [2*3*17] - 3 is prime105 = [3*5*7] - 3 is prime106 = [2*53] - 2 is prime108 = [2*2*3*3*3] - 5 is prime110 = [2*5*11] - 3 is prime111 = [3*37] - 2 is prime112 = [2*2*2*2*7] - 5 is prime114 = [2*3*19] - 3 is prime115 = [5*23] - 2 is prime116 = [2*2*29] - 3 is prime117 = [3*3*13] - 3 is prime118 = [2*59] - 2 is prime119 = [7*17] - 2 is prime120 = [2*2*2*3*5] - 5 is prime
≪ { } 2 120FOR n FACTORS 0 2 3 PICK SIZEFOR j OVER j GET + 2STEP NIPIF ISPRIME?THEN n +ENDNEXT≫ 'TASK' STO{4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120}require"prime"p(1..120).select{|n|n.prime_division.sum(&:last).prime?}
[4, 6, 8, 9, 10, 12, 14, 15, 18, 20, 21, 22, 25, 26, 27, 28, 30, 32, 33, 34, 35, 38, 39, 42, 44, 45, 46, 48, 49, 50, 51, 52, 55, 57, 58, 62, 63, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 82, 85, 86, 87, 91, 92, 93, 94, 95, 98, 99, 102, 105, 106, 108, 110, 111, 112, 114, 115, 116, 117, 118, 119, 120]
Usesprimal
useprimal::Primes;constMAX:u64=120;/// Returns an Option with a tuple => Ok((smaller prime factor, num divided by that prime factor))/// If num is a prime number itself, returns Nonefnextract_prime_factor(num:u64)->Option<(u64,u64)>{letmuti=0;ifprimal::is_prime(num){None}else{loop{letprime=Primes::all().nth(i).unwrap()asu64;ifnum%prime==0{returnSome((prime,num/prime));}else{i+=1;}}}}/// Returns a vector containing all the prime factors of numfnfactorize(num:u64)->Vec<u64>{letmutfactorized=Vec::new();letmutrest=num;whileletSome((prime,factorizable_rest))=extract_prime_factor(rest){factorized.push(prime);rest=factorizable_rest;}factorized.push(rest);factorized}fnmain(){letmutoutput:Vec<u64>=Vec::new();fornumin4..=MAX{ifprimal::is_prime(factorize(num).len()asu64){output.push(num);}}println!("The attractive numbers up to and including 120 are\n{:?}",output);}
The attractive numbers up to and including 120 are[4, 6, 8, 9, 10, 12, 14, 15, 18, 20, 21, 22, 25, 26, 27, 28, 30, 32, 33, 34, 35, 38, 39, 42, 44, 45, 46, 48, 49, 50, 51, 52, 55, 57, 58, 62, 63, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 82, 85, 86, 87, 91, 92, 93, 94, 95, 98, 99, 102, 105, 106, 108, 110, 111, 112, 114, 115, 116, 117, 118, 119, 120]
Best seen in running your browser either byScalaFiddle (ES aka JavaScript, non JVM) orScastie (remote JVM).
objectAttractiveNumbersextendsApp{privatevalmax=120privatevarcount=0privatedefnFactors(n:Int):Int={@scala.annotation.tailrecdeffactors(x:Int,f:Int,acc:Int):Int=if(f*f>x)acc+1elsex%fmatch{case0=>factors(x/f,f,acc+1)case_=>factors(x,f+1,acc)}factors(n,2,0)}privatedefls:Seq[String]=for(i<-4tomax;n=nFactors(i)ifn>=2&&nFactors(n)==1// isPrime(n))yieldf"$i%4d($n)"println(f"The attractive numbers up to and including$max%d are: [number(factors)]\n")ls.zipWithIndex.groupBy{case(_,index)=>index/20}.foreach{case(_,row)=>println(row.map(_._1).mkString)}}
program attractive_numbers; numbers := [n in [2..120] | attractive(n)]; printtab(numbers, 20, 3); proc printtab(list, cols, width); lines := [list(k..cols+k-1) : k in [1, cols+1..#list]]; loop for line in lines do print(+/[lpad(str item, width+1) : item in line]); end loop; end proc; proc attractive(n); return #factorize(#factorize(n)) = 1; end proc; proc factorize(n); factors := []; d := 2; loop until d > n do loop while n mod d = 0 do factors with:= d; n div:= d; end loop; d +:= 1; end loop; return factors; end proc;end program;
4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
funcis_attractive(n){n.bigomega.is_prime}1..120->grep(is_attractive).say
[4, 6, 8, 9, 10, 12, 14, 15, 18, 20, 21, 22, 25, 26, 27, 28, 30, 32, 33, 34, 35, 38, 39, 42, 44, 45, 46, 48, 49, 50, 51, 52, 55, 57, 58, 62, 63, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 82, 85, 86, 87, 91, 92, 93, 94, 95, 98, 99, 102, 105, 106, 108, 110, 111, 112, 114, 115, 116, 117, 118, 119, 120]
importFoundationextensionBinaryInteger{@inlinablepublicvarisAttractive:Bool{returnprimeDecomposition().count.isPrime}@inlinablepublicvarisPrime:Bool{ifself==0||self==1{returnfalse}elseifself==2{returntrue}letmax=Self(ceil((Double(self).squareRoot())))foriinstride(from:2,through:max,by:1){ifself%i==0{returnfalse}}returntrue}@inlinablepublicfuncprimeDecomposition()->[Self]{guardself>1else{return[]}funcstep(_x:Self)->Self{return1+(x<<2)-((x>>1)<<1)}letmaxQ=Self(Double(self).squareRoot())vard:Self=1varq:Self=self&1==0?2:3whileq<=maxQ&&self%q!=0{q=step(d)d+=1}returnq<=maxQ?[q]+(self/q).primeDecomposition():[self]}}letattractive=Array((1...).lazy.filter({$0.isAttractive}).prefix(while:{$0<=120}))print("Attractive numbers up to and including 120:\(attractive)")
Attractive numbers up to and including 120: [4, 6, 8, 9, 10, 12, 14, 15, 18, 20, 21, 22, 25, 26, 27, 28, 30, 32, 33, 34, 35, 38, 39, 42, 44, 45, 46, 48, 49, 50, 51, 52, 55, 57, 58, 62, 63, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 82, 85, 86, 87, 91, 92, 93, 94, 95, 98, 99, 102, 105, 106, 108, 110, 111, 112, 114, 115, 116, 117, 118, 119, 120]
procisPrime{n}{if{$n<2}{return0}if{$n>3}{if{0==($n%2)}{return0}for{setd3}{($d*$d)<=$n}{incrd2}{if{0==($n%$d)}{return0}}}return1;# no divisor found}proccntPF{n}{setcnt0while{0==($n%2)}{setn[expr{$n/2}]incrcnt}for{setd3}{($d*$d)<=$n}{incrd2}{while{0==($n%$d)}{setn[expr{$n/$d}]incrcnt}}if{$n>1}{incrcnt}return$cnt}procshowRange{lohi}{puts"Attractive numbers in range $lo..$hi are:"setk0for{setn$lo}{$n<=$hi}{incrn}{if{[isPrime[cntPF$n]]}{puts-nonewline" [format %3s $n]"incrk}if{$k>=20}{puts""setk0}}if{$k>0}{puts""}}showRange1120
Attractive numbers in range 1..120 are: 4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
boolis_prime(intn){vard=5;if(n<2)returnfalse;if(n%2==0)returnn==2;if(n%3==0)returnn==3;while(d*d<=n){if(n%d==0)returnfalse;d+=2;if(n%d==0)returnfalse;d+=4;}returntrue;}intcount_prime_factors(intn){varcount=0;varf=2;if(n==1)return0;if(is_prime(n))return1;while(true){if(n%f==0){count++;n/=f;if(n==1)returncount;if(is_prime(n))f=n;}elseif(f>=3){f+=2;}else{f=3;}}}voidmain(){constintMAX=120;varn=0;varcount=0;stdout.printf(@"The attractive numbers up to and including $MAX are:\n");for(inti=1;i<=MAX;i++){n=count_prime_factors(i);if(is_prime(n)){stdout.printf("%4d",i);count++;if(count%20==0)stdout.printf("\n");}}stdout.printf("\n");}
The attractive numbers up to and including 120 are: 4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
Option ExplicitPublic Sub AttractiveNumbers()Dim max As Integer, i As Integer, n As Integermax = 120For i = 1 To max n = CountPrimeFactors(i) If IsPrime(n) Then Debug.Print iNext iEnd SubPublic Function IsPrime(ByVal n As Integer) As BooleanDim d As IntegerIsPrime = Trued = 5If n < 2 Then IsPrime = False GoTo FinishEnd IfIf n Mod 2 = 0 Then IsPrime = (n = 2) GoTo FinishEnd IfIf n Mod 3 = 0 Then IsPrime = (n = 3) GoTo FinishEnd IfWhile (d * d <= n) If (n Mod d = 0) Then IsPrime = False d = d + 2 If (n Mod d = 0) Then IsPrime = False d = d + 4WendFinish:End FunctionPublic Function CountPrimeFactors(ByVal n As Integer) As IntegerDim count As Integer, f As IntegerIf n = 1 Then CountPrimeFactors = 0 GoTo Finish2End IfIf (IsPrime(n)) Then CountPrimeFactors = 1 GoTo Finish2End Ifcount = 0f = 2Do While (True) If n Mod f = 0 Then count = count + 1 n = n / f If n = 1 Then CountPrimeFactors = count Exit Do End If If IsPrime(n) Then f = n ElseIf f >= 3 Then f = f + 2 Else f = 3 End IfLoopFinish2:End Function
ModuleModule1ConstMAX=120FunctionIsPrime(nAsInteger)AsBooleanIfn<2ThenReturnFalseIfnMod2=0ThenReturnn=2IfnMod3=0ThenReturnn=3Dimd=5Whiled*d<=nIfnModd=0ThenReturnFalsed+=2IfnModd=0ThenReturnFalsed+=4EndWhileReturnTrueEndFunctionFunctionPrimefactorCount(nAsInteger)AsIntegerIfn=1ThenReturn0IfIsPrime(n)ThenReturn1Dimcount=0Dimf=2WhileTrueIfnModf=0Thencount+=1n/=fIfn=1ThenReturncountIfIsPrime(n)Thenf=nElseIff>=3Thenf+=2Elsef=3EndIfEndWhileThrowNewException("Unexpected")EndFunctionSubMain()Console.WriteLine("The attractive numbers up to and including {0} are:",MAX)Dimi=1Dimcount=0Whilei<=MAXDimn=PrimefactorCount(i)IfIsPrime(n)ThenConsole.Write("{0,4}",i)count+=1IfcountMod20=0ThenConsole.WriteLine()EndIfEndIfi+=1EndWhileConsole.WriteLine()EndSubEndModule
The attractive numbers up to and including 120 are: 4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
fn is_prime(n int) bool { if n < 2 { return false } else if n%2 == 0 { return n == 2 } else if n%3 == 0 { return n == 3 } else { mut d := 5 for d*d <= n { if n%d == 0 { return false } d += 2 if n%d == 0 { return false } d += 4 } return true }}fn count_prime_factors(n int) int { mut nn := n if n == 1 { return 0 } else if is_prime(nn) { return 1 } else { mut count, mut f := 0, 2 for { if nn%f == 0 { count++ nn /= f if nn == 1{ return count } if is_prime(nn) { f = nn } } else if f >= 3{ f += 2 } else { f = 3 } } return count }}fn main() { max := 120 println('The attractive numbers up to and including $max are:') mut count := 0 for i in 1 .. max+1 { n := count_prime_factors(i) if is_prime(n) { print('${i:4}') count++ if count%20 == 0 { println('') } } }}The attractive numbers up to and including 120 are: 4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
import"./fmt"forFmtimport"./math"forIntvarmax=120System.print("The attractive numbers up to and including%(max) are:")varcount=0for(iin1..max){varn=Int.primeFactors(i).countif(Int.isPrime(n)){Fmt.write("$4d",i)count=count+1if(count%20==0)System.print()}}System.print()
The attractive numbers up to and including 120 are: 4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
func IsPrime(N); \Return 'true' if N is primeint N, I;[if N <= 2 then return N = 2;if (N&1) = 0 then \even >2\ return false;for I:= 3 to sqrt(N) do [if rem(N/I) = 0 then return false; I:= I+1; ];return true;];func Factors(N); \Return number of factors for Nint N, Cnt, F;[Cnt:= 0;F:= 2;repeat if rem(N/F) = 0 then [Cnt:= Cnt+1; N:= N/F; ] else F:= F+1;until F > N;return Cnt;];int C, N;[C:= 0;for N:= 4 to 120 do if IsPrime(Factors(N)) then [IntOut(0, N); C:= C+1; if rem(C/10) then ChOut(0, 9\tab\) else CrLf(0); ];]
4 6 8 9 10 12 14 15 18 2021 22 25 26 27 28 30 32 33 3435 38 39 42 44 45 46 48 49 5051 52 55 57 58 62 63 65 66 6869 70 72 74 75 76 77 78 80 8285 86 87 91 92 93 94 95 98 99102 105 106 108 110 111 112 114 115 116117 118 119 120
Using GMP (GNU Multiple Precision Arithmetic Library, probabilisticprimes) because it is easy and fast to test for primeness.
var [const] BI=Import("zklBigNum"); // libGMPfcn attractiveNumber(n){ BI(primeFactors(n).len()).probablyPrime() }println("The attractive numbers up to and including 120 are:");[1..120].filter(attractiveNumber) .apply("%4d".fmt).pump(Void,T(Void.Read,19,False),"println");fcn primeFactors(n){ // Return a list of factors of n acc:=fcn(n,k,acc,maxD){ // k is 2,3,5,7,9,... not optimum if(n==1 or k>maxD) acc.close(); else{ q,r:=n.divr(k); // divr-->(quotient,remainder) if(r==0) return(self.fcn(q,k,acc.write(k),q.toFloat().sqrt())); return(self.fcn(n,k+1+k.isOdd,acc,maxD)) } }(n,2,Sink(List),n.toFloat().sqrt()); m:=acc.reduce('*,1); // mulitply factors if(n!=m) acc.append(n/m); // opps, missed last factor else acc;}The attractive numbers up to and including 120 are: 4 6 8 9 10 12 14 15 18 20 21 22 25 26 27 28 30 32 33 34 35 38 39 42 44 45 46 48 49 50 51 52 55 57 58 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 85 86 87 91 92 93 94 95 98 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120
(u64, u64)> {
let mut i = 0; if primal::is_prime(num) { None } else { loop { let prime = Primes::all().nth(i).unwrap() as u64; if num % prime == 0 { return Some((prime, num / prime)); } else { i += 1; } } }}
/// Returns a vector containing all the prime factors of numfn factorize(num: u64) -> Vec