How to resolve the algorithm Attractive numbers step by step in the ALGOL W programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm Attractive numbers step by step in the ALGOL W programming language
Table of Contents
Problem Statement
A number is an attractive number if the number of its prime factors (whether distinct or not) is also prime.
The number 20, whose prime decomposition is 2 × 2 × 5, is an attractive number because the number of its prime factors (3) is also prime.
Show sequence items up to 120.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Attractive numbers step by step in the ALGOL W programming language
Source code in the algol programming language
% 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.
You may also check:How to resolve the algorithm Greatest common divisor step by step in the MiniScript programming language
You may also check:How to resolve the algorithm Aliquot sequence classifications step by step in the Mathematica / Wolfram Language programming language
You may also check:How to resolve the algorithm Zero to the zero power step by step in the COBOL programming language
You may also check:How to resolve the algorithm Non-decimal radices/Output step by step in the Icon and Unicon programming language
You may also check:How to resolve the algorithm Formatted numeric output step by step in the Forth programming language