Attractive numbers
You are encouraged to solve this task according to the task description, using any language you may know.
A number is an attractive number if the number of its prime factors (whether distinct or not) is also prime.
- Example
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.
- Task
Show sequence items up to 120.
- Reference
-
- The OEIS entry: A063989: Numbers with a prime number of prime divisors.
11l
F is_prime(n)
I n < 2
R 0B
L(i) 2 .. Int(sqrt(n))
I n % i == 0
R 0B
R 1B
F 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] pool
L(each) 0..120
pool.append(get_pfct(each))
[Int] r
L(each) pool
I is_prime(each)
r.append(L.index)
print(r.map(String).join(‘,’))- Output:
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
8080 Assembly
;;; Show attractive numbers up to 120
MAX: equ 120 ; can be up to 255 (8 bit math is used)
;;; CP/M calls
puts: equ 9
bdos: equ 5
org 100h
;;; -- Zero memory ------------------------------------------------
lxi b,fctrs ; page 2
mvi e,2 ; zero out two pages
xra a
mov d,a
zloop: stax b
inx b
dcr d
jnz zloop
dcr e
jnz zloop
;;; -- Generate primes --------------------------------------------
lxi h,plist ; pointer to beginning of primes list
mvi e,2 ; first prime is 2
pstore: mov m,e ; begin prime list
pcand: inr e ; next candidate
jz factor ; if 0, we've rolled over, so we're done
mov l,d ; beginning of primes list (D=0 here)
mov c,m ; C = prime to test against
ptest: mov a,e
ploop: sub c ; test by repeated subtraction
jc notdiv ; if carry, not divisible
jz pcand ; if zero, next candidate
jmp ploop
notdiv: inx h ; get next prime
mov c,m
mov a,c ; is it zero?
ora a
jnz ptest ; if not, test against next prime
jmp pstore ; otherwise, add E to the list of primes
;;; -- Count factors ----------------------------------------------
factor: mvi c,2 ; start with two
fnum: mvi a,MAX ; is candidate beyond maximum?
cmp c
jc output ; then stop
mvi d,0 ; D = number of factors of C
mov l,d ; L = first prime
mov e,c ; E = number we're factorizing
fprim: mvi h,ppage ; H = current prime
mov h,m
ftest: mvi b,0
mov a,e
cpi 1 ; If one, we've counted all the factors
jz nxtfac
fdiv: sub h
jz divi
jc ndivi
inr b
jmp fdiv
divi: inr d ; we found a factor
inr b
mov e,b ; we've removed it, try again
jmp ftest
ndivi: inr l ; not divisible, try next prime
jmp fprim
nxtfac: mov a,d ; store amount of factors
mvi b,fcpage
stax b
inr c ; do next number
jmp fnum
;;; -- Check which numbers are attractive and print them ----------
output: lxi b,fctrs+2 ; start with two
mvi h,ppage ; H = page of primes
onum: mvi a,MAX ; is candidate beyond maximum?
cmp c
rc ; then stop
ldax b ; get amount of factors
mvi l,0 ; start at beginning of prime list
chprm: cmp m ; check against current prime
jz print ; if it's prime, then print the number
inr l ; otherwise, check next prime
jp chprm
next: inr c ; check next number
jmp onum
print: push b ; keep registers
push h
mov a,c ; print number
call printa
pop h ; restore registers
pop b
jmp next
;;; Subroutine: print the number in A
printa: lxi d,num ; DE = string
mvi b,10 ; divisor
digit: mvi c,-1 ; C = quotient
divlp: inr c
sub b
jnc divlp
adi '0'+10 ; make digit
dcx d ; store digit
stax d
mov a,c ; again with new quotient
ora a ; is it zero?
jnz digit ; if not, do next digit
mvi c,puts ; CP/M print string (in DE)
jmp bdos
db '000' ; placeholder for number
num: db ' $'
fcpage: equ 2 ; factors in page 2
ppage: equ 3 ; primes in page 3
fctrs: equ 256*fcpage
plist: equ 256*ppage- Output:
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
ABC
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 factors
HOW TO REPORT attractive n:
REPORT 1 = #factors #factors n
PUT 0 IN col
FOR i IN {1..120}:
IF attractive i:
WRITE i>>5
PUT col+1 IN col
IF col mod 10=0: WRITE /- Output:
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
Action!
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)
FI
RETURN (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
OD
RETURN- Output:
Screenshot from Atari 8-bit computer
Attractive numbers in range 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
Ada
with Ada.Text_IO;
procedure Attractive_Numbers is
function Is_Prime (N : in Natural) return Boolean is
D : Natural := 5;
begin
if N < 2 then return False; end if;
if N mod 2 = 0 then return N = 2; end if;
if N mod 3 = 0 then return N = 3; end if;
while D * D <= N loop
if N mod D = 0 then return False; end if;
D := D + 2;
if N mod D = 0 then return False; end if;
D := D + 4;
end loop;
return True;
end Is_Prime;
function Count_Prime_Factors (N : in Natural) return Natural is
NC : Natural := N;
Count : Natural := 0;
F : Natural := 2;
begin
if NC = 1 then return 0; end if;
if Is_Prime (NC) then return 1; end if;
loop
if NC mod F = 0 then
Count := Count + 1;
NC := NC / F;
if NC = 1 then
return Count;
end if;
if Is_Prime (NC) then F := NC; end if;
elsif F >= 3 then
F := F + 2;
else
F := 3;
end if;
end loop;
end Count_Prime_Factors;
procedure Show_Attractive (Max : in Natural)
is
use Ada.Text_IO;
package Integer_IO is
new Ada.Text_IO.Integer_IO (Integer);
N : Natural;
Count : Natural := 0;
begin
Put_Line ("The attractive numbers up to and including " & Max'Image & " are:");
for I in 1 .. Max loop
N := Count_Prime_Factors (I);
if Is_Prime (N) then
Integer_IO.Put (I, Width => 5);
Count := Count + 1;
if Count mod 20 = 0 then New_Line; end if;
end if;
end loop;
end Show_Attractive;
begin
Show_Attractive (Max => 120);
end Attractive_Numbers;
- 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
ALGOL 68
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- Output:
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 120 Found 74 attractive numbers
ALGOL W
% 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 )
end
end.- Output:
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
AppleScript
on isPrime(n)
if (n < 4) then return (n > 1)
if ((n mod 2 is 0) or (n mod 3 is 0)) then return false
repeat with i from 5 to (n ^ 0.5) div 1 by 6
if ((n mod i is 0) or (n mod (i + 2) is 0)) then return false
end repeat
return true
end isPrime
on primeFactorCount(n)
set x to n
set counter to 0
if (n > 1) then
repeat while (n mod 2 = 0)
set counter to counter + 1
set n to n div 2
end repeat
repeat while (n mod 3 = 0)
set counter to counter + 1
set n to n div 3
end repeat
set i to 5
set limit to (n ^ 0.5) div 1
repeat until (i > limit)
repeat while (n mod i = 0)
set counter to counter + 1
set n to n div i
end repeat
tell (i + 2) to repeat while (n mod it = 0)
set counter to counter + 1
set n to n div it
end repeat
set i to i + 6
set limit to (n ^ 0.5) div 1
end repeat
if (n > 1) then set counter to counter + 1
end if
return counter
end primeFactorCount
-- Task code:
local output, n
set output to {}
repeat with n from 1 to 120
if (isPrime(primeFactorCount(n))) then set end of output to n
end repeat
return output
- Output:
{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!
Arturo
attractive?: function [x] -> prime? size factors.prime x
print select 1..120 => attractive?
- Output:
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
AutoHotkey
AttractiveNumbers(n){
c := prime_numbers(n).count()
if c = 1
return
return isPrime(c)
}
isPrime(n){
return (prime_numbers(n).count() = 1)
}
prime_numbers(n) {
if (n <= 3)
return [n]
ans := []
done := false
while !done
{
if !Mod(n,2){
ans.push(2)
n /= 2
continue
}
if !Mod(n,3) {
ans.push(3)
n /= 3
continue
}
if (n = 1)
return ans
sr := sqrt(n)
done := true
; try to divide the checked number by all numbers till its square root.
i := 6
while (i <= sr+6){
if !Mod(n, i-1) { ; is n divisible by i-1?
ans.push(i-1)
n /= i-1
done := false
break
}
if !Mod(n, i+1) { ; is n divisible by i+1?
ans.push(i+1)
n /= i+1
done := false
break
}
i += 6
}
}
ans.push(n)
return ans
}
Examples:
c:= 0
loop
{
if AttractiveNumbers(A_Index)
c++, result .= SubStr(" " A_Index, -2) . (Mod(c, 20) ? " " : "`n")
if A_Index = 120
break
}
MsgBox, 262144, ,% result
return
- Output:
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
AWK
# syntax: GAWK -f ATTRACTIVE_NUMBERS.AWK
# converted from C
BEGIN {
limit = 120
printf("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)
}
function count_prime_factors(n, count,f) {
f = 2
if (n == 1) { return(0) }
if (is_prime(n)) { return(1) }
while (1) {
if (!(n % f)) {
count++
n /= f
if (n == 1) { return(count) }
if (is_prime(n)) { f = n }
}
else if (f >= 3) { f += 2 }
else { f = 3 }
}
}
function is_prime(x, i) {
if (x <= 1) {
return(0)
}
for (i=2; i<=int(sqrt(x)); i++) {
if (x % i == 0) {
return(0)
}
}
return(1)
}
- Output:
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
BASIC
10 DEFINT A-Z
20 M=120
30 DIM C(M): C(0)=-1: C(1)=-1
40 FOR I=2 TO SQR(M)
50 IF NOT C(I) THEN FOR J=I+I TO M STEP I: C(J)=-1: NEXT
60 NEXT
70 FOR I=2 TO M
80 N=I: C=0
90 FOR J=2 TO M
100 IF NOT C(J) THEN IF N MOD J=0 THEN N=N\J: C=C+1: GOTO 100
110 NEXT
120 IF NOT C(C) THEN PRINT I,
130 NEXT
- Output:
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
BCPL
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')
$)- Output:
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
C
#include <stdio.h>
#define TRUE 1
#define FALSE 0
#define MAX 120
typedef int bool;
bool is_prime(int n) {
int d = 5;
if (n < 2) return FALSE;
if (!(n % 2)) return n == 2;
if (!(n % 3)) return n == 3;
while (d *d <= n) {
if (!(n % d)) return FALSE;
d += 2;
if (!(n % d)) return FALSE;
d += 4;
}
return TRUE;
}
int count_prime_factors(int n) {
int count = 0, f = 2;
if (n == 1) return 0;
if (is_prime(n)) return 1;
while (TRUE) {
if (!(n % f)) {
count++;
n /= f;
if (n == 1) return count;
if (is_prime(n)) f = n;
}
else if (f >= 3) f += 2;
else f = 3;
}
}
int main() {
int i, 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");
return 0;
}
- 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
C#
using System;
namespace AttractiveNumbers {
class Program {
const int MAX = 120;
static bool IsPrime(int n) {
if (n < 2) return false;
if (n % 2 == 0) return n == 2;
if (n % 3 == 0) return n == 3;
int d = 5;
while (d * d <= n) {
if (n % d == 0) return false;
d += 2;
if (n % d == 0) return false;
d += 4;
}
return true;
}
static int PrimeFactorCount(int n) {
if (n == 1) return 0;
if (IsPrime(n)) return 1;
int count = 0;
int 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;
}
}
}
static void Main(string[] args) {
Console.WriteLine("The attractive numbers up to and including {0} are:", MAX);
int i = 1;
int count = 0;
while (i <= MAX) {
int n = PrimeFactorCount(i);
if (IsPrime(n)) {
Console.Write("{0,4}", i);
if (++count % 20 == 0) Console.WriteLine();
}
++i;
}
Console.WriteLine();
}
}
}
- 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
C++
#include <iostream>
#include <iomanip>
#define MAX 120
using namespace std;
bool is_prime(int n) {
if (n < 2) return false;
if (!(n % 2)) return n == 2;
if (!(n % 3)) return n == 3;
int d = 5;
while (d *d <= n) {
if (!(n % d)) return false;
d += 2;
if (!(n % d)) return false;
d += 4;
}
return true;
}
int count_prime_factors(int n) {
if (n == 1) return 0;
if (is_prime(n)) return 1;
int count = 0, f = 2;
while (true) {
if (!(n % f)) {
count++;
n /= f;
if (n == 1) return count;
if (is_prime(n)) f = n;
}
else if (f >= 3) f += 2;
else f = 3;
}
}
int main() {
cout << "The attractive numbers up to and including " << MAX << " are:" << endl;
for (int i = 1, count = 0; i <= MAX; ++i) {
int n = count_prime_factors(i);
if (is_prime(n)) {
cout << setw(4) << i;
if (!(++count % 20)) cout << endl;
}
}
cout << endl;
return 0;
}
- 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
CLU
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 sieve
n_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_factors
start_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
end
end start_up- Output:
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
COBOL
IDENTIFICATION DIVISION.
PROGRAM-ID. ATTRACTIVE-NUMBERS.
DATA DIVISION.
WORKING-STORAGE SECTION.
77 MAXIMUM PIC 999 VALUE 120.
01 SIEVE-DATA VALUE SPACES.
03 MARKER PIC X OCCURS 120 TIMES.
88 PRIME VALUE SPACE.
03 SIEVE-MAX PIC 999.
03 COMPOSITE PIC 999.
03 CANDIDATE PIC 999.
01 FACTORIZE-DATA.
03 FACTOR-NUM PIC 999.
03 FACTORS PIC 999.
03 FACTOR PIC 999.
03 QUOTIENT PIC 999V999.
03 FILLER REDEFINES QUOTIENT.
05 FILLER PIC 999.
05 DECIMAL PIC 999.
01 OUTPUT-FORMAT.
03 OUT-NUM PIC ZZZ9.
03 OUT-LINE PIC X(72) VALUE SPACES.
03 COL-PTR PIC 99 VALUE 1.
PROCEDURE DIVISION.
BEGIN.
PERFORM SIEVE.
PERFORM CHECK-ATTRACTIVE
VARYING CANDIDATE FROM 2 BY 1
UNTIL CANDIDATE IS GREATER THAN MAXIMUM.
PERFORM WRITE-LINE.
STOP RUN.
CHECK-ATTRACTIVE.
MOVE CANDIDATE TO FACTOR-NUM.
PERFORM FACTORIZE.
IF PRIME(FACTORS), PERFORM ADD-TO-OUTPUT.
ADD-TO-OUTPUT.
MOVE CANDIDATE TO OUT-NUM.
STRING OUT-NUM DELIMITED BY SIZE INTO OUT-LINE
WITH POINTER COL-PTR.
IF COL-PTR IS EQUAL TO 73, PERFORM WRITE-LINE.
WRITE-LINE.
DISPLAY OUT-LINE.
MOVE SPACES TO OUT-LINE.
MOVE 1 TO COL-PTR.
FACTORIZE SECTION.
BEGIN.
MOVE ZERO TO FACTORS.
PERFORM DIVIDE-PRIME
VARYING FACTOR FROM 2 BY 1
UNTIL FACTOR IS GREATER THAN MAXIMUM.
GO TO DONE.
DIVIDE-PRIME.
IF PRIME(FACTOR),
DIVIDE FACTOR-NUM BY FACTOR GIVING QUOTIENT,
IF DECIMAL IS EQUAL TO ZERO,
ADD 1 TO FACTORS,
MOVE QUOTIENT TO FACTOR-NUM,
GO TO DIVIDE-PRIME.
DONE.
EXIT.
SIEVE SECTION.
BEGIN.
MOVE 'X' TO MARKER(1).
DIVIDE MAXIMUM BY 2 GIVING SIEVE-MAX.
PERFORM SET-COMPOSITES THRU SET-COMPOSITES-LOOP
VARYING CANDIDATE FROM 2 BY 1
UNTIL CANDIDATE IS GREATER THAN SIEVE-MAX.
GO TO DONE.
SET-COMPOSITES.
MULTIPLY CANDIDATE BY 2 GIVING COMPOSITE.
SET-COMPOSITES-LOOP.
IF COMPOSITE IS NOT GREATER THAN MAXIMUM,
MOVE 'X' TO MARKER(COMPOSITE),
ADD CANDIDATE TO COMPOSITE,
GO TO SET-COMPOSITES-LOOP.
DONE.
EXIT.
- Output:
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
Comal
0010 FUNC factors#(n#) CLOSED
0020 count#:=0
0030 WHILE n# MOD 2=0 DO n#:=n# DIV 2;count#:+1
0040 fac#:=3
0050 WHILE fac#<=n# DO
0060 WHILE n# MOD fac#=0 DO n#:=n# DIV fac#;count#:+1
0070 fac#:+2
0080 ENDWHILE
0090 RETURN count#
0100 ENDFUNC factors#
0110 //
0120 ZONE 4
0130 seen#:=0
0140 FOR i#:=2 TO 120 DO
0150 IF factors#(factors#(i#))=1 THEN
0160 PRINT i#,
0170 seen#:+1
0180 IF seen# MOD 18=0 THEN PRINT
0190 ENDIF
0200 ENDFOR i#
0210 PRINT
0220 END
- Output:
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
Common Lisp
(defun attractivep (n)
(primep (length (factors n))) )
; For primality testing we can use different methods, but since we have to define factors that's what we'll use
(defun primep (n)
(= (length (factors n)) 1) )
(defun factors (n)
"Return a list of factors of N."
(when (> n 1)
(loop with max-d = (isqrt n)
for d = 2 then (if (evenp d) (+ d 1) (+ d 2)) do
(cond ((> d max-d) (return (list n))) ; n is prime
((zerop (rem n d)) (return (cons d (factors (truncate n d)))))))))
- Output:
(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
Cowgol
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();- Output:
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
Craft Basic
for x = 1 to 120
let n = x
let c = 0
do
if int(n mod 2) = 0 then
let n = int(n / 2)
let c = c + 1
endif
wait
loop int(n mod 2) = 0
for i = 3 to sqrt(n) step 2
do
if int(n mod i) = 0 then
let n = int(n / i)
let c = c + 1
endif
wait
loop int(n mod i) = 0
next i
if n > 2 then
let c = c + 1
endif
if prime(c) then
print x, " ",
endif
next x
- Output:
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
D
import std.stdio;
enum MAX = 120;
bool isPrime(int n) {
if (n < 2) return false;
if (n % 2 == 0) return n == 2;
if (n % 3 == 0) return n == 3;
int d = 5;
while (d * d <= n) {
if (n % d == 0) return false;
d += 2;
if (n % d == 0) return false;
d += 4;
}
return true;
}
int primeFactorCount(int n) {
if (n == 1) return 0;
if (isPrime(n)) return 1;
int count;
int 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;
}
}
}
void main() {
writeln("The attractive numbers up to and including ", MAX, " are:");
int i = 1;
int count;
while (i <= MAX) {
int n = primeFactorCount(i);
if (isPrime(n)) {
writef("%4d", i);
if (++count % 20 == 0) writeln;
}
++i;
}
writeln;
}
- 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
Delphi
See #Pascal.
Draco
/* 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
od
corp
/* 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;
count
corp
/* 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
od
corp- Output:
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
EasyLang
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 & " "
.
.F#
// attractive_numbers.fsx
// taken from Primality by trial division
let rec primes =
let next_state s = Some(s, s + 2)
Seq.cache
(Seq.append
(seq[ 2; 3; 5 ])
(Seq.unfold next_state 7
|> Seq.filter is_prime))
and is_prime number =
let rec is_prime_core number current limit =
let cprime = primes |> Seq.item current
if cprime >= limit then true
elif number % cprime = 0 then false
else is_prime_core number (current + 1) (number/cprime)
if number = 2 then true
elif number < 2 then false
else is_prime_core number 0 number
// taken from Prime decomposition task and modified to add
let count_prime_divisors n =
let rec loop c n count =
let p = Seq.item n primes
if c < (p * p) then count
elif c % p = 0 then loop (c / p) n (count + 1)
else loop c (n + 1) count
loop n 0 1
let is_attractive = count_prime_divisors >> is_prime
let print_iter i n =
if i % 10 = 9
then printfn "%d" n
else printf "%d\t" n
[1..120]
|> List.filter is_attractive
|> List.iteri print_iter
- Output:
>dotnet fsi attractive_numbers.fsx 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 %
Factor
USING: formatting grouping io math.primes math.primes.factors
math.ranges sequences ;
"The attractive numbers up to and including 120 are:" print
120 [1,b] [ factors length prime? ] filter 20 <groups>
[ [ "%4d" printf ] each nl ] each
- 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
Fortran
program attractive_numbers
use iso_fortran_env, only: output_unit
implicit none
integer, parameter :: maximum=120, line_break=20
integer :: i, counter
write(output_unit,'(A,x,I0,x,A)') "The attractive numbers up to and including", maximum, "are:"
counter = 0
do i = 1, maximum
if (is_prime(count_prime_factors(i))) then
write(output_unit,'(I0,x)',advance="no") i
counter = counter + 1
if (modulo(counter, line_break) == 0) write(output_unit,*)
end if
end do
write(output_unit,*)
contains
pure function is_prime(n)
integer, intent(in) :: n
logical :: is_prime
integer :: d
is_prime = .false.
d = 5
if (n < 2) return
if (modulo(n, 2) == 0) then
is_prime = n==2
return
end if
if (modulo(n, 3) == 0) then
is_prime = n==3
return
end if
do
if (d**2 > n) then
is_prime = .true.
return
end if
if (modulo(n, d) == 0) then
is_prime = .false.
return
end if
d = d + 2
if (modulo(n, d) == 0) then
is_prime = .false.
return
end if
d = d + 4
end do
is_prime = .true.
end function is_prime
pure function count_prime_factors(n)
integer, intent(in) :: n
integer :: count_prime_factors
integer :: i, f
count_prime_factors = 0
if (n == 1) return
if (is_prime(n)) then
count_prime_factors = 1
return
end if
count_prime_factors = 0
f = 2
i = n
do
if (modulo(i, f) == 0) then
count_prime_factors = count_prime_factors + 1
i = i/f
if (i == 1) exit
if (is_prime(i)) f = i
else if (f >= 3) then
f = f + 2
else
f = 3
end if
end do
end function count_prime_factors
end program attractive_numbers
- 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
FreeBASIC
Const limite = 120
Declare Function esPrimo(n As Integer) As Boolean
Declare Function ContandoFactoresPrimos(n As Integer) As Integer
Function esPrimo(n As Integer) As Boolean
If n < 2 Then Return false
If n Mod 2 = 0 Then Return n = 2
If n Mod 3 = 0 Then Return n = 3
Dim As Integer d = 5
While d * d <= n
If n Mod d = 0 Then Return false
d += 2
If n Mod d = 0 Then Return false
d += 4
Wend
Return true
End Function
Function ContandoFactoresPrimos(n As Integer) As Integer
If n = 1 Then Return false
If esPrimo(n) Then Return true
Dim As Integer f = 2, contar = 0
While true
If n Mod f = 0 Then
contar += 1
n = n / f
If n = 1 Then Return contar
If esPrimo(n) Then f = n
Elseif f >= 3 Then
f += 2
Else
f = 3
End If
Wend
End Function
' Mostrar la sucencia de números atractivos hasta 120.
Dim As Integer i = 1, longlinea = 0
Print "Los numeros atractivos hasta e incluyendo"; limite; " son: "
While i <= limite
Dim As Integer n = ContandoFactoresPrimos(i)
If esPrimo(n) Then
Print Using "####"; i;
longlinea += 1: If longlinea Mod 20 = 0 Then Print ""
End If
i += 1
Wend
End
- Output:
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
Frink
println[select[2 to 120, {|x| !isPrime[x] and isPrime[length[factorFlat[x]]]}]]- Output:
[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æ
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 its website.
In this 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.
FutureBasic
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
next
end fn = YES
local 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 = count
void 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
next
end fn
fn AttractiveNumbers( 120 )
HandleEvents- Output:
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
Go
Simple functions to test for primality and to count prime factors suffice here.
package main
import "fmt"
func isPrime(n int) bool {
switch {
case n < 2:
return false
case n%2 == 0:
return n == 2
case n%3 == 0:
return n == 3
default:
d := 5
for d*d <= n {
if n%d == 0 {
return false
}
d += 2
if n%d == 0 {
return false
}
d += 4
}
return true
}
}
func countPrimeFactors(n int) int {
switch {
case n == 1:
return 0
case isPrime(n):
return 1
default:
count, f := 0, 2
for {
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 count
}
}
func main() {
const max = 120
fmt.Println("The attractive numbers up to and including", max, "are:")
count := 0
for i := 1; i <= max; i++ {
n := countPrimeFactors(i)
if isPrime(n) {
fmt.Printf("%4d", i)
count++
if count % 20 == 0 {
fmt.Println()
}
}
}
fmt.Println()
}
- 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
Groovy
class AttractiveNumbers {
static boolean isPrime(int n) {
if (n < 2) return false
if (n % 2 == 0) return n == 2
if (n % 3 == 0) return n == 3
int d = 5
while (d * d <= n) {
if (n % d == 0) return false
d += 2
if (n % d == 0) return false
d += 4
}
return true
}
static int countPrimeFactors(int n) {
if (n == 1) return 0
if (isPrime(n)) return 1
int 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
}
}
static void main(String[] args) {
final int max = 120
printf("The attractive numbers up to and including %d are:\n", max)
int count = 0
for (int i = 1; i <= max; ++i) {
int n = countPrimeFactors(i)
if (isPrime(n)) {
printf("%4d", i)
if (++count % 20 == 0) println()
}
}
println()
}
}
- 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
Haskell
import Data.Numbers.Primes
import Data.Bool (bool)
attractiveNumbers :: [Integer]
attractiveNumbers =
[1 ..] >>= (bool [] . return) <*> (isPrime . length . primeFactors)
main :: IO ()
main = print $ takeWhile (<= 120) attractiveNumbers
Or equivalently, as a list comprehension:
import Data.Numbers.Primes
attractiveNumbers :: [Integer]
attractiveNumbers =
[ x
| x <- [1 ..]
, isPrime (length (primeFactors x)) ]
main :: IO ()
main = print $ takeWhile (<= 120) attractiveNumbers
Or simply:
import Data.Numbers.Primes
attractiveNumbers :: [Integer]
attractiveNumbers =
filter
(isPrime . length . primeFactors)
[1 ..]
main :: IO ()
main = print $ takeWhile (<= 120) attractiveNumbers
- Output:
[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]
Insitux
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))J
echo (#~ (1 p: ])@#@q:) >:i.120
- Output:
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
JavaScript
(() => {
'use strict';
// attractiveNumbers :: () -> Gen [Int]
const attractiveNumbers = () =>
// An infinite series of attractive numbers.
filter(
compose(isPrime, length, primeFactors)
)(enumFrom(1));
// ----------------------- TEST -----------------------
// main :: IO ()
const main = () =>
showCols(10)(
takeWhile(ge(120))(
attractiveNumbers()
)
);
// ---------------------- PRIMES ----------------------
// isPrime :: Int -> Bool
const isPrime = n => {
// True if n is prime.
if (2 === n || 3 === n) {
return true
}
if (2 > n || 0 === n % 2) {
return false
}
if (9 > n) {
return true
}
if (0 === n % 3) {
return false
}
return !enumFromThenTo(5)(11)(
1 + Math.floor(Math.pow(n, 0.5))
).some(x => 0 === n % x || 0 === n % (2 + x));
};
// primeFactors :: Int -> [Int]
const primeFactors = n => {
// A list of the prime factors of n.
const
go = x => {
const
root = 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];
return m > root ? (
[x]
) : ([m].concat(go(Math.floor(x / m))));
},
step = x => 1 + (x << 2) - ((x >> 1) << 1);
return go(n);
};
// ---------------- GENERIC FUNCTIONS -----------------
// chunksOf :: Int -> [a] -> [[a]]
const chunksOf = n =>
xs => enumFromThenTo(0)(n)(
xs.length - 1
).reduce(
(a, i) => a.concat([xs.slice(i, (n + i))]),
[]
);
// compose (<<<) :: (b -> c) -> (a -> b) -> a -> c
const compose = (...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.
let v = x;
while (true) {
yield v;
v = 1 + v;
}
}
// enumFromThenTo :: Int -> Int -> Int -> [Int]
const enumFromThenTo = x1 =>
x2 => y => {
const d = x2 - x1;
return Array.from({
length: Math.floor(y - x2) / d + 2
}, (_, i) => x1 + (d * i));
};
// filter :: (a -> Bool) -> Gen [a] -> [a]
const filter = p => xs => {
function* go() {
let x = xs.next();
while (!x.done) {
let v = x.value;
if (p(v)) {
yield v
}
x = xs.next();
}
}
return go(xs);
};
// ge :: Ord a => a -> a -> Bool
const ge = x =>
// True if x >= y
y => x >= y;
// justifyRight :: Int -> Char -> String -> String
const justifyRight = 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] -> a
const last = xs =>
// The last item of a list.
0 < xs.length ? xs.slice(-1)[0] : undefined;
// length :: [a] -> Int
const length = 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' === typeof xs) ? (
xs.length
) : Infinity;
// map :: (a -> b) -> [a] -> [b]
const map = 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] -> String
const showCols = w => xs => {
const
ys = xs.map(str),
mx = last(ys).length;
return unlines(chunksOf(w)(ys).map(
row => row.map(justifyRight(mx)(' ')).join(' ')
))
};
// str :: a -> String
const str = x =>
x.toString();
// takeWhile :: (a -> Bool) -> Gen [a] -> [a]
const takeWhile = p => xs => {
const ys = [];
let
nxt = xs.next(),
v = nxt.value;
while (!nxt.done && p(v)) {
ys.push(v);
nxt = xs.next();
v = nxt.value
}
return ys;
};
// unlines :: [String] -> String
const unlines = 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 -> a
const until = p => f => x => {
let v = x;
while (!p(v)) v = f(v);
return v;
};
// MAIN ---
return main();
})();
- Output:
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
Java
public class Attractive {
static boolean is_prime(int n) {
if (n < 2) return false;
if (n % 2 == 0) return n == 2;
if (n % 3 == 0) return n == 3;
int d = 5;
while (d *d <= n) {
if (n % d == 0) return false;
d += 2;
if (n % d == 0) return false;
d += 4;
}
return true;
}
static int count_prime_factors(int n) {
if (n == 1) return 0;
if (is_prime(n)) return 1;
int count = 0, f = 2;
while (true) {
if (n % f == 0) {
count++;
n /= f;
if (n == 1) return count;
if (is_prime(n)) f = n;
}
else if (f >= 3) f += 2;
else f = 3;
}
}
public static void main(String[] args) {
final int max = 120;
System.out.printf("The attractive numbers up to and including %d are:\n", max);
for (int i = 1, count = 0; i <= max; ++i) {
int n = count_prime_factors(i);
if (is_prime(n)) {
System.out.printf("%4d", i);
if (++count % 20 == 0) System.out.println();
}
}
System.out.println();
}
}
- 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
jq
Works with gojq, the Go implementation of jq
This entry uses:
- `is_prime` as defined at Erdős primes on RC
- `prime_factors` as defined at Smith numbers on RC
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)- Output:
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]
Julia
using Primes
# 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)
- Output:
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]
Kotlin
// Version 1.3.21
const val MAX = 120
fun isPrime(n: Int) : Boolean {
if (n < 2) return false
if (n % 2 == 0) return n == 2
if (n % 3 == 0) return n == 3
var d : Int = 5
while (d * d <= n) {
if (n % d == 0) return false
d += 2
if (n % d == 0) return false
d += 4
}
return true
}
fun countPrimeFactors(n: Int) =
when {
n == 1 -> 0
isPrime(n) -> 1
else -> {
var nn = n
var count = 0
var f = 2
while (true) {
if (nn % f == 0) {
count++
nn /= f
if (nn == 1) break
if (isPrime(nn)) f = nn
} else if (f >= 3) {
f += 2
} else {
f = 3
}
}
count
}
}
fun main() {
println("The attractive numbers up to and including $MAX are:")
var count = 0
for (i in 1..MAX) {
val n = countPrimeFactors(i)
if (isPrime(n)) {
System.out.printf("%4d", i)
if (++count % 20 == 0) println()
}
}
println()
}
- 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
LLVM
; 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" = comdat any
$"FORMAT_NUMBER" = comdat any
$"NEWLINE_STR" = comdat any
@"ATTRACTIVE_STR" = linkonce_odr unnamed_addr constant [52 x i8] c"The attractive numbers up to and including %d are:\0A\00", comdat, align 1
@"FORMAT_NUMBER" = linkonce_odr unnamed_addr constant [4 x i8] c"%4d\00", comdat, align 1
@"NEWLINE_STR" = linkonce_odr unnamed_addr constant [2 x i8] c"\0A\00", comdat, align 1
;--- The declaration for the external C printf function.
declare i32 @printf(i8*, ...)
; Function Attrs: noinline nounwind optnone uwtable
define zeroext i1 @is_prime(i32) #0 {
%2 = alloca i1, align 1 ;-- allocate return value
%3 = alloca i32, align 4 ;-- allocate n
%4 = alloca i32, align 4 ;-- allocate d
store i32 %0, i32* %3, align 4 ;-- store local copy of n
store i32 5, i32* %4, align 4 ;-- store 5 in d
%5 = load i32, i32* %3, align 4 ;-- load n
%6 = icmp slt i32 %5, 2 ;-- n < 2
br i1 %6, label %nlt2, label %niseven
nlt2:
store i1 false, i1* %2, align 1 ;-- store false in return value
br label %exit
niseven:
%7 = load i32, i32* %3, align 4 ;-- load n
%8 = srem i32 %7, 2 ;-- n % 2
%9 = icmp ne i32 %8, 0 ;-- (n % 2) != 0
br i1 %9, label %odd, label %even
even:
%10 = load i32, i32* %3, align 4 ;-- load n
%11 = icmp eq i32 %10, 2 ;-- n == 2
store i1 %11, i1* %2, align 1 ;-- store (n == 2) in return value
br label %exit
odd:
%12 = load i32, i32* %3, align 4 ;-- load n
%13 = srem i32 %12, 3 ;-- n % 3
%14 = icmp ne i32 %13, 0 ;-- (n % 3) != 0
br i1 %14, label %loop, label %div3
div3:
%15 = load i32, i32* %3, align 4 ;-- load n
%16 = icmp eq i32 %15, 3 ;-- n == 3
store i1 %16, i1* %2, align 1 ;-- store (n == 3) in return value
br label %exit
loop:
%17 = load i32, i32* %4, align 4 ;-- load d
%18 = load i32, i32* %4, align 4 ;-- load d
%19 = mul nsw i32 %17, %18 ;-- d * d
%20 = load i32, i32* %3, align 4 ;-- load n
%21 = icmp sle i32 %19, %20 ;-- (d * d) <= n
br i1 %21, label %first, label %prime
first:
%22 = load i32, i32* %3, align 4 ;-- load n
%23 = load i32, i32* %4, align 4 ;-- load d
%24 = srem i32 %22, %23 ;-- n % d
%25 = icmp ne i32 %24, 0 ;-- (n % d) != 0
br i1 %25, label %second, label %notprime
second:
%26 = load i32, i32* %4, align 4 ;-- load d
%27 = add nsw i32 %26, 2 ;-- increment d by 2
store i32 %27, i32* %4, align 4 ;-- store d
%28 = load i32, i32* %3, align 4 ;-- load n
%29 = load i32, i32* %4, align 4 ;-- load d
%30 = srem i32 %28, %29 ;-- n % d
%31 = icmp ne i32 %30, 0 ;-- (n % d) != 0
br i1 %31, label %loop_end, label %notprime
loop_end:
%32 = load i32, i32* %4, align 4 ;-- load d
%33 = add nsw i32 %32, 4 ;-- increment d by 4
store i32 %33, i32* %4, align 4 ;-- store d
br label %loop
notprime:
store i1 false, i1* %2, align 1 ;-- store false in return value
br label %exit
prime:
store i1 true, i1* %2, align 1 ;-- store true in return value
br label %exit
exit:
%34 = load i1, i1* %2, align 1 ;-- load return value
ret i1 %34
}
; Function Attrs: noinline nounwind optnone uwtable
define i32 @count_prime_factors(i32) #0 {
%2 = alloca i32, align 4 ;-- allocate return value
%3 = alloca i32, align 4 ;-- allocate n
%4 = alloca i32, align 4 ;-- allocate count
%5 = alloca i32, align 4 ;-- allocate f
store i32 %0, i32* %3, align 4 ;-- store local copy of n
store i32 0, i32* %4, align 4 ;-- store zero in count
store i32 2, i32* %5, align 4 ;-- store 2 in f
%6 = load i32, i32* %3, align 4 ;-- load n
%7 = icmp eq i32 %6, 1 ;-- n == 1
br i1 %7, label %eq1, label %ne1
eq1:
store i32 0, i32* %2, align 4 ;-- store zero in return value
br label %exit
ne1:
%8 = load i32, i32* %3, align 4 ;-- load n
%9 = call zeroext i1 @is_prime(i32 %8) ;-- is n prime?
br i1 %9, label %prime, label %loop
prime:
store i32 1, i32* %2, align 4 ;-- store a in return value
br label %exit
loop:
%10 = load i32, i32* %3, align 4 ;-- load n
%11 = load i32, i32* %5, align 4 ;-- load f
%12 = srem i32 %10, %11 ;-- n % f
%13 = icmp ne i32 %12, 0 ;-- (n % f) != 0
br i1 %13, label %br2, label %br1
br1:
%14 = load i32, i32* %4, align 4 ;-- load count
%15 = add nsw i32 %14, 1 ;-- increment count
store i32 %15, i32* %4, align 4 ;-- store count
%16 = load i32, i32* %5, align 4 ;-- load f
%17 = load i32, i32* %3, align 4 ;-- load n
%18 = sdiv i32 %17, %16 ;-- n / f
store i32 %18, i32* %3, align 4 ;-- n = n / f
%19 = load i32, i32* %3, align 4 ;-- load n
%20 = icmp eq i32 %19, 1 ;-- n == 1
br i1 %20, label %br1_1, label %br1_2
br1_1:
%21 = load i32, i32* %4, align 4 ;-- load count
store i32 %21, i32* %2, align 4 ;-- store the count in the return value
br label %exit
br1_2:
%22 = load i32, i32* %3, align 4 ;-- load n
%23 = call zeroext i1 @is_prime(i32 %22) ;-- is n prime?
br i1 %23, label %br1_3, label %loop
br1_3:
%24 = load i32, i32* %3, align 4 ;-- load n
store i32 %24, i32* %5, align 4 ;-- f = n
br label %loop
br2:
%25 = load i32, i32* %5, align 4 ;-- load f
%26 = icmp sge i32 %25, 3 ;-- f >= 3
br i1 %26, label %br2_1, label %br3
br2_1:
%27 = load i32, i32* %5, align 4 ;-- load f
%28 = add nsw i32 %27, 2 ;-- increment f by 2
store i32 %28, i32* %5, align 4 ;-- store f
br label %loop
br3:
store i32 3, i32* %5, align 4 ;-- store 3 in f
br label %loop
exit:
%29 = load i32, i32* %2, align 4 ;-- load return value
ret i32 %29
}
; Function Attrs: noinline nounwind optnone uwtable
define i32 @main() #0 {
%1 = alloca i32, align 4 ;-- allocate i
%2 = alloca i32, align 4 ;-- allocate n
%3 = alloca i32, align 4 ;-- count
store i32 0, i32* %3, align 4 ;-- store zero in count
%4 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([52 x i8], [52 x i8]* @"ATTRACTIVE_STR", i32 0, i32 0), i32 120)
store i32 1, i32* %1, align 4 ;-- store 1 in i
br label %loop
loop:
%5 = load i32, i32* %1, align 4 ;-- load i
%6 = icmp sle i32 %5, 120 ;-- i <= 120
br i1 %6, label %loop_body, label %exit
loop_body:
%7 = load i32, i32* %1, align 4 ;-- load i
%8 = call i32 @count_prime_factors(i32 %7) ;-- count factors of i
store i32 %8, i32* %2, align 4 ;-- store factors in n
%9 = call zeroext i1 @is_prime(i32 %8) ;-- is n prime?
br i1 %9, label %prime_branch, label %loop_inc
prime_branch:
%10 = load i32, i32* %1, align 4 ;-- load i
%11 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @"FORMAT_NUMBER", i32 0, i32 0), i32 %10)
%12 = load i32, i32* %3, align 4 ;-- load count
%13 = add nsw i32 %12, 1 ;-- increment count
store i32 %13, i32* %3, align 4 ;-- store count
%14 = srem i32 %13, 20 ;-- count % 20
%15 = icmp ne i32 %14, 0 ;-- (count % 20) != 0
br i1 %15, label %loop_inc, label %row_end
row_end:
%16 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([2 x i8], [2 x i8]* @"NEWLINE_STR", i32 0, i32 0))
br label %loop_inc
loop_inc:
%17 = load i32, i32* %1, align 4 ;-- load i
%18 = add nsw i32 %17, 1 ;-- increment i
store i32 %18, i32* %1, align 4 ;-- store i
br label %loop
exit:
%19 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([2 x i8], [2 x i8]* @"NEWLINE_STR", i32 0, i32 0))
ret i32 0
}
attributes #0 = { noinline nounwind optnone uwtable "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" }
- 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
Lua
-- Returns true if x is prime, and false otherwise
function isPrime (x)
if x < 2 then return false end
if x < 4 then return true end
if x % 2 == 0 then return false end
for d = 3, math.sqrt(x), 2 do
if x % d == 0 then return false end
end
return true
end
-- Compute the prime factors of n
function factors (n)
local facList, divisor, count = {}, 1
if n < 2 then return facList end
while not isPrime(n) do
while not isPrime(divisor) do divisor = divisor + 1 end
count = 0
while n % divisor == 0 do
n = n / divisor
table.insert(facList, divisor)
end
divisor = divisor + 1
if n == 1 then return facList end
end
table.insert(facList, n)
return facList
end
-- Main procedure
for i = 1, 120 do
if isPrime(#factors(i)) then io.write(i .. "\t") end
end
- Output:
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
Maple
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);- Output:
[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]
Mathematica / Wolfram Language
ClearAll[AttractiveNumberQ]
AttractiveNumberQ[n_Integer] := FactorInteger[n][[All, 2]] // Total // PrimeQ
Reap[Do[If[AttractiveNumberQ[i], Sow[i]], {i, 120}]][[2, 1]]
- Output:
{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}
Maxima
AttractiveNumber(N):=block([Q:0],
if not primep(N) then (
if primep(apply("+", map(lambda([Z], Z[2]), ifactors(N)))) then Q: N
), Q
)$
delete(0, makelist(AttractiveNumber(K), K, 1, 120));
Using sublist
attractivep(n):=block(ifactors(n),apply("+",map(second,%%)),if primep(%%) then true)$
sublist(makelist(i,i,120),attractivep);
- Output:
[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]
MiniScript
isPrime = function(n)
if n < 2 then return false
if n < 4 then return true
for i in range(2,floor(n ^ 0.5))
if n % i == 0 then return false
end for
return true
end function
countFactors = function(n)
cnt = 0
for i in range(2, n)
while n % i == 0
cnt += 1
n /= i
end while
end for
return cnt
end function
isAttractive = function(n)
if n < 1 then return false
factorCnt = countFactors(n)
return isPrime(factorCnt)
end function
numbers = []
for i in range(2, 120)
if isAttractive(i) then numbers.push(i)
end for
print numbers.join(", ")
- Output:
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
Miranda
main :: [sys_message]
main = [Stdout (show (filter attractive [1..120]))]
attractive :: num->bool
attractive n = #factors (#factors n) = 1
factors :: 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- Output:
[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]
Modula-2
MODULE AttractiveNumbers;
FROM InOut IMPORT WriteCard, WriteLn;
CONST
Max = 120;
VAR
n, col: CARDINAL;
Prime: ARRAY [1..Max] OF BOOLEAN;
PROCEDURE Sieve;
VAR i, j: CARDINAL;
BEGIN
Prime[1] := FALSE;
FOR i := 2 TO Max DO
Prime[i] := TRUE;
END;
FOR i := 2 TO Max DIV 2 DO
IF Prime[i] THEN
j := i*2;
WHILE j <= Max DO
Prime[j] := FALSE;
j := j + i;
END;
END;
END;
END Sieve;
PROCEDURE Factors(n: CARDINAL): CARDINAL;
VAR i, factors: CARDINAL;
BEGIN
factors := 0;
FOR i := 2 TO Max DO
IF i > n THEN
RETURN factors;
END;
IF Prime[i] THEN
WHILE n MOD i = 0 DO
n := n DIV i;
factors := factors + 1;
END;
END;
END;
RETURN factors;
END Factors;
BEGIN
Sieve();
col := 0;
FOR n := 2 TO Max DO
IF Prime[Factors(n)] THEN
WriteCard(n, 4);
col := col + 1;
IF col MOD 15 = 0 THEN
WriteLn();
END;
END;
END;
WriteLn();
END AttractiveNumbers.
- Output:
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
Nanoquery
MAX = 120
def is_prime(n)
d = 5
if (n < 2)
return false
end
if (n % 2) = 0
return n = 2
end
if (n % 3) = 0
return n = 3
end
while (d * d) <= n
if n % d = 0
return false
end
d += 2
if n % d = 0
return false
end
d += 4
end
return true
end
def count_prime_factors(n)
count = 0; f = 2
if n = 1
return 0
end
if is_prime(n)
return 1
end
while true
if (n % f) = 0
count += 1
n /= f
if n = 1
return count
end
if is_prime(n)
f = n
end
else if f >= 3
f += 2
else
f = 3
end
end
end
i = 0; n = 0; count = 0
println 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 += 1
if (count % 20) = 0
println
end
end
end
println- 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
NewLisp
The factor 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 (factor n)) 1))
(define (attractive? n)
(prime? (length (factor n))))
;
(filter attractive? (sequence 2 120))
- Output:
(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)
Nim
import strformat
const MAX = 120
proc isPrime(n: int): bool =
var d = 5
if n < 2:
return false
if n mod 2 == 0:
return n == 2
if n mod 3 == 0:
return n == 3
while d * d <= n:
if n mod d == 0:
return false
inc d, 2
if n mod d == 0:
return false
inc d, 4
return true
proc countPrimeFactors(n_in: int): int =
var count = 0
var f = 2
var n = n_in
if n == 1:
return 0
if isPrime(n):
return 1
while true:
if n mod f == 0:
inc count
n = n div f
if n == 1:
return count
if isPrime(n):
f = n
elif (f >= 3):
inc f, 2
else:
f = 3
proc main() =
var n, count: int = 0
echo fmt"The attractive numbers up to and including {MAX} are:"
for i in 1..MAX:
n = countPrimeFactors(i)
if isPrime(n):
write(stdout, fmt"{i:4d}")
inc count
if count mod 20 == 0:
write(stdout, "\n")
write(stdout, "\n")
main()
- 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
Objeck
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;
}
}- 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
Odin
package main
import "core:fmt"
main :: proc() {
const_max :: 120
fmt.println("\nAttractive numbers up to and including", const_max, "are: ")
count := 0
for i in 1 ..= const_max {
n := countPrimeFactors(i)
if isPrime(n) {
fmt.print(i, " ")
count += 1
if count % 20 == 0 {
fmt.println()
}
}
}
fmt.println()
}
/* definitions */
isPrime :: proc(n: int) -> bool {
switch {
case n < 2:
return false
case n % 2 == 0:
return n == 2
case n % 3 == 0:
return n == 3
case:
d := 5
for d * d <= n {
if n % d == 0 {
return false
}
d += 2
if n % d == 0 {
return false
}
d += 4
}
return true
}
}
countPrimeFactors :: proc(n: int) -> int {
n := n
switch {
case n == 1:
return 0
case isPrime(n):
return 1
case:
count, f := 0, 2
for {
if n % f == 0 {
count += 1
n /= f
if n == 1 {
return count
}
if isPrime(n) {
f = n
}
} else if f >= 3 {
f += 2
} else {
f = 3
}
}
return count
}
}
- Output:
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
Pascal
same procedure as in http://rosettacode.org/wiki/Abundant,_deficient_and_perfect_number_classifications
program AttractiveNumbers;
{ 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}
uses
sysutils;//timing
const
cTextMany = ' with many factors ';
cText2 = ' with only two factors ';
cText1 = ' with only one factor ';
type
tValue = LongWord;
tpValue = ^tValue;
tPower = array[0..63] of tValue;//2^64
var
power : tPower;
sieve : array of byte;
function NextPotCnt(p: tValue):tValue;
//return the first power <> 0
//power == n to base prim
var
i : NativeUint;
begin
result := 0;
repeat
i := power[result];
Inc(i);
IF i < p then
BREAK
else
begin
i := 0;
power[result] := 0;
inc(result);
end;
until false;
power[result] := i;
inc(result);
end;
procedure InitSieveWith2;
//the prime 2, because its the first one, is the one,
//which can can be speed up tremendously, by moving
var
pSieve : pByte;
CopyWidth,lmt : NativeInt;
Begin
pSieve := @sieve[0];
Lmt := High(sieve);
sieve[1] := 0;
sieve[2] := 1; // aka 2^1 -> one factor
CopyWidth := 2;
while CopyWidth*2 <= Lmt do
Begin
// copy idx 1,2 to 3,4 | 1..4 to 5..8 | 1..8 to 9..16
move(pSieve[1],pSieve[CopyWidth+1],CopyWidth);
// 01 -> 0101 -> 01020102-> 0102010301020103
inc(CopyWidth,CopyWidth);//*2
//increment the factor of last element by one.
inc(pSieve[CopyWidth]);
//idx 12 1234 12345678
//value 01 -> 0102 -> 01020103-> 0102010301020104
end;
//copy the rest
move(pSieve[1],pSieve[CopyWidth+1],Lmt-CopyWidth);
//mark 0,1 not prime, 255 factors are today not possible 2^255 >> Uint64
sieve[0]:= 255;
sieve[1]:= 255;
sieve[2]:= 0; // make prime again
end;
procedure OutCntTime(T:TDateTime;txt:String;cnt:NativeInt);
Begin
writeln(cnt:12,txt,T*86400:10:3,' s');
end;
procedure sievefactors;
var
T0 : TDateTime;
pSieve : pByte;
i,j,i2,k,lmt,cnt : NativeUInt;
Begin
InitSieveWith2;
pSieve := @sieve[0];
Lmt := High(sieve);
//Divide into 3 section
//first i*i*i<= lmt with time expensive NextPotCnt
T0 := now;
cnt := 0;
//third root of limit calculate only once, no comparison ala while i*i*i<= lmt do
k := trunc(exp(ln(Lmt)/3));
For i := 3 to k do
if pSieve[i] = 0 then
Begin
inc(cnt);
j := 2*i;
fillChar(Power,Sizeof(Power),#0);
Power[0] := 1;
repeat
inc(pSieve[j],NextPotCnt(i));
inc(j,i);
until j > lmt;
end;
OutCntTime(now-T0,cTextMany,cnt);
T0 := now;
//second i*i <= lmt
cnt := 0;
i := k+1;
k := trunc(sqrt(Lmt));
For i := i to k do
if pSieve[i] = 0 then
Begin
//first increment all multiples of prime by one
inc(cnt);
j := 2*i;
repeat
inc(pSieve[j]);
inc(j,i);
until j>lmt;
//second increment all multiples prime*prime by one
i2 := i*i;
j := i2;
repeat
inc(pSieve[j]);
inc(j,i2);
until j>lmt;
end;
OutCntTime(now-T0,cText2,cnt);
T0 := now;
//third i*i > lmt -> only one new factor
cnt := 0;
inc(k);
For i := k to Lmt shr 1 do
if pSieve[i] = 0 then
Begin
inc(cnt);
j := 2*i;
repeat
inc(pSieve[j]);
inc(j,i);
until j>lmt;
end;
OutCntTime(now-T0,cText1,cnt);
end;
const
smallLmt = 120;
//needs 1e10 Byte = 10 Gb maybe someone got 128 Gb :-) nearly linear time
BigLimit = 10*1000*1000*1000;
var
T0,T : TDateTime;
i,cnt,lmt : NativeInt;
Begin
setlength(sieve,smallLmt+1);
sievefactors;
cnt := 0;
For i := 2 to smallLmt do
Begin
if sieve[sieve[i]] = 0 then
Begin
write(i:4);
inc(cnt);
if cnt>19 then
Begin
writeln;
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;
repeat
repeat
inc(i);
{IF sieve[sieve[i]] = 0 then inc(cnt); takes double time is not relevant}
inc(cnt,ORD(sieve[sieve[i]] = 0));
until i = lmt;
writeln(lmt:11,cnt:12);
lmt := 10*lmt;
until lmt >High(sieve);
T := now-T;
writeln('time counting : ',T*86400 :8:3,' s');
writeln('time total : ',(now-T0)*86400 :8:3,' s');
end.
- Output:
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 120
time 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 s
time sieving : 200.813 s
10 5
100 60
1000 636
10000 6396
100000 63255
1000000 623232
10000000 6137248
100000000 60472636
1000000000 596403124
10000000000 5887824685
time counting : 6.130 s
time total : 208.022 s
real 3m28,044s
Perl
use ntheory <is_prime factor>;
is_prime +factor $_ and print "$_ " for 1..120;
- Output:
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
Phix
function attractive(integer lim) sequence s = {} for i=1 to lim do integer n = length(prime_factors(i,true)) if is_prime(n) then s &= i end if end for return s end function sequence s = attractive(120) printf(1,"There are %d attractive numbers up to and including %d:\n",{length(s),120}) pp(s,{pp_IntCh,false}) for i=3 to 6 do atom t0 = time() integer p = power(10,i), l = length(attractive(p)) string e = elapsed(time()-t0) printf(1,"There are %,d attractive numbers up to %,d (%s)\n",{l,p,e}) end for
- Output:
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)
PHP
<?php
function isPrime ($x) {
if ($x < 2) return false;
if ($x < 4) return true;
if ($x % 2 == 0) return false;
for ($d = 3; $d < sqrt($x); $d++) {
if ($x % $d == 0) return false;
}
return true;
}
function countFacs ($n) {
$count = 0;
$divisor = 1;
if ($n < 2) return 0;
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." ";
}
?>
- Output:
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
PL/I
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;- Output:
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
PL/M
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;
EOF- Output:
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
Prolog
prime_factors(N, Factors):-
S is sqrt(N),
prime_factors(N, Factors, S, 2).
prime_factors(1, [], _, _):-!.
prime_factors(N, [P|Factors], S, P):-
P =< S,
0 is N mod P,
!,
M is N // P,
prime_factors(M, Factors, S, P).
prime_factors(N, Factors, S, P):-
Q is P + 1,
Q =< S,
!,
prime_factors(N, Factors, S, Q).
prime_factors(N, [N], _, _).
is_prime(2):-!.
is_prime(N):-
0 is N mod 2,
!,
fail.
is_prime(N):-
N > 2,
S is sqrt(N),
\+is_composite(N, S, 3).
is_composite(N, S, P):-
P =< S,
0 is N mod P,
!.
is_composite(N, S, P):-
Q is P + 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]),
(0 is C mod 20 -> nl ; true),
C1 is C + 1
;
C1 = C
),
Next is From + 1,
print_attractive_numbers(Next, To, C1).
main:-
print_attractive_numbers(1, 120, 1).
- Output:
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
PureBasic
#MAX=120
Dim prime.b(#MAX)
FillMemory(@prime(),#MAX,#True,#PB_Byte) : FillMemory(@prime(),2,#False,#PB_Byte)
For i=2 To Int(Sqr(#MAX)) : n=i*i : While n<#MAX : prime(n)=#False : n+i : Wend : Next
Procedure.i pfCount(n.i)
Shared prime()
If n=1 : ProcedureReturn 0 : EndIf
If prime(n) : ProcedureReturn 1 : EndIf
count=0 : f=2
Repeat
If n%f=0 : count+1 : n/f
If n=1 : ProcedureReturn count : EndIf
If prime(n) : f=n : EndIf
ElseIf f>=3 : f+2
Else : f=3
EndIf
ForEver
EndProcedure
OpenConsole()
PrintN("The attractive numbers up to and including "+Str(#MAX)+" are:")
For i=1 To #MAX
If prime(pfCount(i))
Print(RSet(Str(i),4)) : count+1 : If count%20=0 : PrintN("") : EndIf
EndIf
Next
PrintN("") : Input()
- 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
Python
Procedural
from sympy import sieve # library for primes
def get_pfct(n):
i = 2; factors = []
while i * i <= n:
if n % i:
i += 1
else:
n //= i
factors.append(i)
if n > 1:
factors.append(n)
return len(factors)
sieve.extend(110) # first 110 primes...
primes=sieve._list
pool=[]
for each in xrange(0,121):
pool.append(get_pfct(each))
for i,each in enumerate(pool):
if each in primes:
print i,
- Output:
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
Functional
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'''
from itertools import chain, count, takewhile
from functools import reduce
# attractiveNumbers :: () -> [Int]
def attractiveNumbers():
'''A non-finite stream of attractive numbers.
(OEIS A063989)
'''
return filter(
compose(
isPrime,
len,
primeDecomposition
),
count(1)
)
# TEST ----------------------------------------------------
def main():
'''Attractive numbers drawn from the range [1..120]'''
for row in chunksOf(15)(list(
takewhile(
lambda x: 120 >= x,
attractiveNumbers()
)
)):
print(' '.join(map(
compose(justifyRight(3)(' '), str),
row
)))
# GENERAL FUNCTIONS ---------------------------------------
# chunksOf :: Int -> [a] -> [[a]]
def chunksOf(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.
'''
return lambda xs: reduce(
lambda a, i: a + [xs[i:n + i]],
range(0, len(xs), n), []
) if 0 < n else []
# compose :: ((a -> a), ...) -> (a -> a)
def compose(*fs):
'''Composition, from right to left,
of a series of functions.
'''
return lambda x: reduce(
lambda a, f: f(a),
fs[::-1], x
)
# We only need light implementations
# of prime functions here:
# primeDecomposition :: Int -> [Int]
def primeDecomposition(n):
'''List of integers representing the
prime decomposition of n.
'''
def go(n, p):
return [p] + go(n // p, p) if (
0 == n % p
) else []
return list(chain.from_iterable(map(
lambda p: go(n, p) if isPrime(p) else [],
range(2, 1 + n)
)))
# isPrime :: Int -> Bool
def isPrime(n):
'''True if n is prime.'''
if n in (2, 3):
return True
if 2 > n or 0 == n % 2:
return False
if 9 > n:
return True
if 0 == n % 3:
return False
return not any(map(
lambda x: 0 == n % x or 0 == n % (2 + x),
range(5, 1 + int(n ** 0.5), 6)
))
# justifyRight :: Int -> Char -> String -> String
def justifyRight(n):
'''A string padded at left to length n,
using the padding character c.
'''
return lambda c: lambda s: s.rjust(n, c)
# MAIN ---
if __name__ == '__main__':
main()
- Output:
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
Quackery
primefactors is defined at Prime decomposition.
[ primefactors size
primefactors size 1 = ] is attractive ( n --> b )
120 times
[ i^ 1+ attractive if
[ i^ 1+ echo sp ] ]- Output:
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
R
is_prime <- function(num) {
if (num < 2) return(FALSE)
if (num %% 2 == 0) return(num == 2)
if (num %% 3 == 0) return(num == 3)
d <- 5
while (d*d <= num) {
if (num %% d == 0) return(FALSE)
d <- d + 2
if (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 <- 0
f <- 2
while (TRUE) {
if (num %% f == 0) {
count <- count + 1
num <- num / f
if (num == 1) return(count)
if (is_prime(num)) f <- num
}
else if (f >= 3) f <- f + 2
else f <- 3
}
}
max <- 120
cat("The attractive numbers up to and including",max,"are:\n")
count <- 0
for (i in 1:max) {
n <- count_prime_factors(i);
if (is_prime(n)) {
cat(i," ", sep = "")
count <- count + 1
}
}
- 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
Racket
#lang racket
(require math/number-theory)
(define attractive? (compose1 prime? prime-omega))
(filter attractive? (range 1 121))
- Output:
(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)
Raku
(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 that could be used. This algorithm is well suited to finding arbitrary attractive numbers though.
use Lingua::EN::Numbers;
use ntheory:from<Perl5> <factor is_prime>;
sub display ($n,$m) { ($n..$m).grep: (~*).&factor.elems.&is_prime }
sub count ($n,$m) { +($n..$m).grep: (~*).&factor.elems.&is_prime }
# The Task
put "Attractive numbers from 1 to 120:\n" ~
display(1, 120)».fmt("%3d").rotor(20, :partial).join: "\n";
# Robusto!
for 1, 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" ~
comma count $a, $b
}
- Output:
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 99 102 105 106 108 110 111 112 114 115 116 117 118 119 120 Count of attractive numbers from 1 to 1,000: 636 Count of attractive numbers from 1 to 10,000: 6,396 Count of attractive numbers from 1 to 100,000: 63,255 Count of attractive numbers from 9,444,732,965,739,290,427,393 to 9,444,732,965,739,290,427,492: 58
REXX
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.*/
parse arg N . /*get optional argument from the C.L. */
if N=='' | N=="," then N= 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.*/
call genP 100 /*gen 100 primes (high= 541); overkill.*/
sw= linesize() - 1 /*SW: is the usable screen width. */
if \cnt then say 'attractive numbers up to and including ' commas(N) " are:"
#= 0 /*number of attractive #'s (so far). */
$= /*a list of attractive numbers (so far)*/
do j=1 for N; if @.j then iterate /*Is it a low prime? Then skip number.*/
a= cFact(j) /*call cFact to count the factors in J.*/
if \@.a then iterate /*if # of factors not prime, then skip.*/
#= # + 1 /*bump number of attractive #'s found. */
if cnt then iterate /*if not displaying numbers, skip list.*/
cj= commas(j); _= $ cj /*append a commatized number to $ list.*/
if length(_)>sw then do; say strip($); $= cj; end /*display a line of numbers.*/
else $= _ /*append the latest number. */
end /*j*/
if $\=='' & \cnt then say strip($) /*display any residual numbers in list.*/
say; say commas(#) ' attractive numbers found up to and including ' commas(N)
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
cFact: procedure; parse arg z 1 oz; if z<2 then return z /*if Z too small, return Z.*/
#= 0 /*#: is the number of factors (so far)*/
do while z//2==0; #= #+1; z= z%2; end /*maybe add the factor of two. */
do while z//3==0; #= #+1; z= z%3; end /* " " " " " three.*/
do while z//5==0; #= #+1; z= z%5; end /* " " " " " five. */
do while z//7==0; #= #+1; z= z%7; end /* " " " " " seven.*/
/* [↑] reduce Z by some low primes. */
do k=11 by 6 while k<=z /*insure that K isn't divisible by 3.*/
parse var k '' -1 _ /*obtain the last decimal digit of K. */
if _\==5 then do while z//k==0; #= #+1; z= z%k; end /*maybe reduce Z.*/
if _ ==3 then iterate /*Next number ÷ by 5? Skip. ____ */
if k*k>oz then leave /*are we greater than the √ OZ ? */
y= k + 2 /*get next divisor, hopefully a prime.*/
do while z//y==0; #= #+1; z= z%y; end /*maybe reduce Z.*/
end /*k*/
if z\==1 then return # + 1 /*if residual isn't unity, then add one*/
return # /*return the number of factors in OZ. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ?
/*──────────────────────────────────────────────────────────────────────────────────────*/
genP: procedure expose @.; parse arg n; @.=0; @.2= 1; @.3= 1; p= 2
do j=3 by 2 until p==n; do k=3 by 2 until k*k>j; if j//k==0 then iterate j
end /*k*/; @.j = 1; p= p + 1
end /*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.
- output when using the default input:
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 74 attractive numbers found up to and including 120
- output when using the input of: -10000
6,396 attractive numbers found up to and including 10,000
- output when using the input of: -100000
63,255 attractive numbers found up to and including 100,000
- output when using the input of: -1000000
623,232 attractive numbers found up to and including 1,000,000
Ring
# Project: Attractive Numbers
decomp = []
nump = 0
see "Attractive Numbers up to 120:" + nl
while nump < 120
decomp = []
nump = nump + 1
for 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
ok
next
if 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
ok
next
ok
end
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- Output:
Attractive Numbers up to 120: 4 = [2*2] - 2 is prime 6 = [2*3] - 2 is prime 8 = [2*2*2] - 3 is prime 9 = [3*3] - 2 is prime 10 = [2*5] - 2 is prime 12 = [2*2*3] - 3 is prime 14 = [2*7] - 2 is prime 15 = [3*5] - 2 is prime 18 = [2*3*3] - 3 is prime 20 = [2*2*5] - 3 is prime ... ... ... 102 = [2*3*17] - 3 is prime 105 = [3*5*7] - 3 is prime 106 = [2*53] - 2 is prime 108 = [2*2*3*3*3] - 5 is prime 110 = [2*5*11] - 3 is prime 111 = [3*37] - 2 is prime 112 = [2*2*2*2*7] - 5 is prime 114 = [2*3*19] - 3 is prime 115 = [5*23] - 2 is prime 116 = [2*2*29] - 3 is prime 117 = [3*3*13] - 3 is prime 118 = [2*59] - 2 is prime 119 = [7*17] - 2 is prime 120 = [2*2*2*3*5] - 5 is prime
RPL
≪ { }
2 120 FOR n
FACTORS 0
2 3 PICK SIZE FOR j OVER j GET + 2 STEP
NIP
IF ISPRIME? THEN n + END
NEXT
≫ 'TASK' STO
- Output:
{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}
Ruby
require "prime"
p (1..120).select{|n| n.prime_division.sum(&:last).prime? }
- Output:
[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]
Rust
Uses primal
use primal::Primes;
const MAX: 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 None
fn extract_prime_factor(num: u64) -> Option<(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 num
fn factorize(num: u64) -> Vec<u64> {
let mut factorized = Vec::new();
let mut rest = num;
while let Some((prime, factorizable_rest)) = extract_prime_factor(rest) {
factorized.push(prime);
rest = factorizable_rest;
}
factorized.push(rest);
factorized
}
fn main() {
let mut output: Vec<u64> = Vec::new();
for num in 4 ..= MAX {
if primal::is_prime(factorize(num).len() as u64) {
output.push(num);
}
}
println!("The attractive numbers up to and including 120 are\n{:?}", output);
}
- 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]
Scala
- Output:
Best seen in running your browser either by ScalaFiddle (ES aka JavaScript, non JVM) or Scastie (remote JVM).
object AttractiveNumbers extends App {
private val max = 120
private var count = 0
private def nFactors(n: Int): Int = {
@scala.annotation.tailrec
def factors(x: Int, f: Int, acc: Int): Int =
if (f * f > x) acc + 1
else
x % f match {
case 0 => factors(x / f, f, acc + 1)
case _ => factors(x, f + 1, acc)
}
factors(n, 2, 0)
}
private def ls: Seq[String] =
for (i <- 4 to max;
n = nFactors(i)
if n >= 2 && nFactors(n) == 1 // isPrime(n)
) yield f"$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) }
}
SETL
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;- Output:
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
Sidef
func is_attractive(n) {
n.bigomega.is_prime
}
1..120 -> grep(is_attractive).say
- Output:
[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]
Swift
import Foundation
extension BinaryInteger {
@inlinable
public var isAttractive: Bool {
return primeDecomposition().count.isPrime
}
@inlinable
public var isPrime: Bool {
if self == 0 || self == 1 {
return false
} else if self == 2 {
return true
}
let max = Self(ceil((Double(self).squareRoot())))
for i in stride(from: 2, through: max, by: 1) {
if self % i == 0 {
return false
}
}
return true
}
@inlinable
public func primeDecomposition() -> [Self] {
guard self > 1 else { return [] }
func step(_ x: Self) -> Self {
return 1 + (x << 2) - ((x >> 1) << 1)
}
let maxQ = Self(Double(self).squareRoot())
var d: Self = 1
var q: Self = self & 1 == 0 ? 2 : 3
while q <= maxQ && self % q != 0 {
q = step(d)
d += 1
}
return q <= maxQ ? [q] + (self / q).primeDecomposition() : [self]
}
}
let attractive = Array((1...).lazy.filter({ $0.isAttractive }).prefix(while: { $0 <= 120 }))
print("Attractive numbers up to and including 120: \(attractive)")
- Output:
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]
Tcl
proc isPrime {n} {
if {$n < 2} {
return 0
}
if {$n > 3} {
if {0 == ($n % 2)} {
return 0
}
for {set d 3} {($d * $d) <= $n} {incr d 2} {
if {0 == ($n % $d)} {
return 0
}
}
}
return 1 ;# no divisor found
}
proc cntPF {n} {
set cnt 0
while {0 == ($n % 2)} {
set n [expr {$n / 2}]
incr cnt
}
for {set d 3} {($d * $d) <= $n} {incr d 2} {
while {0 == ($n % $d)} {
set n [expr {$n / $d}]
incr cnt
}
}
if {$n > 1} {
incr cnt
}
return $cnt
}
proc showRange {lo hi} {
puts "Attractive numbers in range $lo..$hi are:"
set k 0
for {set n $lo} {$n <= $hi} {incr n} {
if {[isPrime [cntPF $n]]} {
puts -nonewline " [format %3s $n]"
incr k
}
if {$k >= 20} {
puts ""
set k 0
}
}
if {$k > 0} {
puts ""
}
}
showRange 1 120
- Output:
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
Vala
bool is_prime(int n) {
var d = 5;
if (n < 2) return false;
if (n % 2 == 0) return n == 2;
if (n % 3 == 0) return n == 3;
while (d * d <= n) {
if (n % d == 0) return false;
d += 2;
if (n % d == 0) return false;
d += 4;
}
return true;
}
int count_prime_factors(int n) {
var count = 0;
var f = 2;
if (n == 1) return 0;
if (is_prime(n)) return 1;
while (true) {
if (n % f == 0) {
count++;
n /= f;
if (n == 1) return count;
if (is_prime(n)) f = n;
} else if (f >= 3) {
f += 2;
} else {
f = 3;
}
}
}
void main() {
const int MAX = 120;
var n = 0;
var count = 0;
stdout.printf(@"The attractive numbers up to and including $MAX are:\n");
for (int i = 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");
}
- 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
VBA
Option Explicit
Public Sub AttractiveNumbers()
Dim max As Integer, i As Integer, n As Integer
max = 120
For i = 1 To max
n = CountPrimeFactors(i)
If IsPrime(n) Then Debug.Print i
Next i
End Sub
Public Function IsPrime(ByVal n As Integer) As Boolean
Dim d As Integer
IsPrime = True
d = 5
If n < 2 Then
IsPrime = False
GoTo Finish
End If
If n Mod 2 = 0 Then
IsPrime = (n = 2)
GoTo Finish
End If
If n Mod 3 = 0 Then
IsPrime = (n = 3)
GoTo Finish
End If
While (d * d <= n)
If (n Mod d = 0) Then IsPrime = False
d = d + 2
If (n Mod d = 0) Then IsPrime = False
d = d + 4
Wend
Finish:
End Function
Public Function CountPrimeFactors(ByVal n As Integer) As Integer
Dim count As Integer, f As Integer
If n = 1 Then
CountPrimeFactors = 0
GoTo Finish2
End If
If (IsPrime(n)) Then
CountPrimeFactors = 1
GoTo Finish2
End If
count = 0
f = 2
Do 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 If
Loop
Finish2:
End FunctionVisual Basic .NET
Module Module1
Const MAX = 120
Function IsPrime(n As Integer) As Boolean
If n < 2 Then Return False
If n Mod 2 = 0 Then Return n = 2
If n Mod 3 = 0 Then Return n = 3
Dim d = 5
While d * d <= n
If n Mod d = 0 Then Return False
d += 2
If n Mod d = 0 Then Return False
d += 4
End While
Return True
End Function
Function PrimefactorCount(n As Integer) As Integer
If n = 1 Then Return 0
If IsPrime(n) Then Return 1
Dim count = 0
Dim f = 2
While True
If n Mod f = 0 Then
count += 1
n /= f
If n = 1 Then Return count
If IsPrime(n) Then f = n
ElseIf f >= 3 Then
f += 2
Else
f = 3
End If
End While
Throw New Exception("Unexpected")
End Function
Sub Main()
Console.WriteLine("The attractive numbers up to and including {0} are:", MAX)
Dim i = 1
Dim count = 0
While i <= MAX
Dim n = PrimefactorCount(i)
If IsPrime(n) Then
Console.Write("{0,4}", i)
count += 1
If count Mod 20 = 0 Then
Console.WriteLine()
End If
End If
i += 1
End While
Console.WriteLine()
End Sub
End Module
- 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
V (Vlang)
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('')
}
}
}
}- 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
Wren
import "./fmt" for Fmt
import "./math" for Int
var max = 120
System.print("The attractive numbers up to and including %(max) are:")
var count = 0
for (i in 1..max) {
var n = Int.primeFactors(i).count
if (Int.isPrime(n)) {
Fmt.write("$4d", i)
count = count + 1
if (count%20 == 0) System.print()
}
}
System.print()
- 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
XPL0
func IsPrime(N); \Return 'true' if N is prime
int 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 N
int 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);
];
]- Output:
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
zkl
Using GMP (GNU Multiple Precision Arithmetic Library, probabilistic primes) because it is easy and fast to test for primeness.
var [const] BI=Import("zklBigNum"); // libGMP
fcn 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");Using Prime decomposition#zkl
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;
}- 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
(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 num fn factorize(num: u64) -> Vec
Categories:
- Programming Tasks
- Solutions by Programming Task
- 11l
- 8080 Assembly
- ABC
- Action!
- Action! Sieve of Eratosthenes
- Ada
- ALGOL 68
- ALGOL 68-primes
- ALGOL W
- AppleScript
- Arturo
- AutoHotkey
- AWK
- BASIC
- BCPL
- C
- C sharp
- C++
- CLU
- COBOL
- Comal
- Common Lisp
- Cowgol
- Craft Basic
- D
- Delphi
- Draco
- EasyLang
- F Sharp
- Factor
- Fortran
- FreeBASIC
- Frink
- Fōrmulæ
- FutureBasic
- Go
- Groovy
- Haskell
- Insitux
- J
- JavaScript
- Java
- Jq
- Julia
- Kotlin
- LLVM
- Lua
- Maple
- Mathematica
- Wolfram Language
- Maxima
- MiniScript
- Miranda
- Modula-2
- Nanoquery
- NewLisp
- Nim
- Objeck
- Odin
- Pascal
- Perl
- Ntheory
- Phix
- PHP
- PL/I
- PL/M
- Prolog
- PureBasic
- Python
- Quackery
- R
- Racket
- Raku
- REXX
- Ring
- RPL
- Ruby
- Rust
- Scala
- SETL
- Sidef
- Swift
- Tcl
- Vala
- VBA
- Visual Basic .NET
- V (Vlang)
- Wren
- Wren-fmt
- Wren-math
- XPL0
- Zkl