Product of min and max prime factors
Product of min and max prime factors is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
Exactly as the task title implies.
- Task
- Find and display the product of the minimum and maximum prime factors for the terms 1 through 100, inclusive.
- For some unknown reason, the term for 1 is defined to be 1.
- An equal case could be made that it should be 0 in my opinion.
- A even stronger case that it should be 'undefined' or NaN. ¯\_(ツ)_/¯
- See also
ALGOL 68
Constructs a tables if min and max prime factors.
BEGIN # find the product of the min and max prime factors of some numbers #
INT max number = 100; # maximum number we will consider #
# sieve the primes to max number #
[ 0 : max number ]BOOL prime;
prime[ 0 ] := prime[ 1 ] := FALSE;
prime[ 2 ] := TRUE;
FOR i FROM 3 BY 2 TO UPB prime DO prime[ i ] := TRUE OD;
FOR i FROM 4 BY 2 TO UPB prime DO prime[ i ] := FALSE OD;
FOR i FROM 3 BY 2 TO ENTIER sqrt( UPB prime ) DO
IF prime[ i ] THEN
FOR s FROM i * i BY i + i TO UPB prime DO prime[ s ] := FALSE OD
FI
OD;
# construct tables of the minimum and maximum prime factors of #
# numbers up to max number #
[ 1 : max number ]INT min pf; FOR i TO UPB min pf DO min pf[ i ] := 0 OD;
[ 1 : max number ]INT max pf; FOR i TO UPB min pf DO max pf[ i ] := 0 OD;
min pf[ 1 ] := 1;
max pf[ 1 ] := 1;
FOR i TO max number DO
IF prime[ i ] THEN
FOR j FROM i BY i TO UPB min pf DO
IF min pf[ j ] = 0 THEN min pf[ j ] := i FI;
max pf[ j ] := i
OD
FI
OD;
# print the products of the min and max prime factors #
FOR i TO max number DO
print( ( whole( min pf[ i ] * max pf[ i ], -5 ) ) );
IF i MOD 10 = 0 THEN print( ( newline ) ) FI
OD
END
- Output:
1 4 9 4 25 6 49 4 9 10 121 6 169 14 15 4 289 6 361 10 21 22 529 6 25 26 9 14 841 10 961 4 33 34 35 6 1369 38 39 10 1681 14 1849 22 15 46 2209 6 49 10 51 26 2809 6 55 14 57 58 3481 10 3721 62 21 4 65 22 4489 34 69 14 5041 6 5329 74 15 38 77 26 6241 10 9 82 6889 14 85 86 87 22 7921 10 91 46 93 94 95 6 9409 14 33 10
C++
#include <iomanip>
#include <iostream>
#include <utility>
auto min_max_prime_factors(unsigned int n) {
unsigned int min_factor = 1;
unsigned int max_factor = 1;
if ((n & 1) == 0) {
while ((n & 1) == 0)
n >>= 1;
min_factor = 2;
max_factor = 2;
}
for (unsigned int p = 3; p * p <= n; p += 2) {
if (n % p == 0) {
while (n % p == 0)
n /= p;
if (min_factor == 1)
min_factor = p;
max_factor = p;
}
}
if (n > 1) {
if (min_factor == 1)
min_factor = n;
max_factor = n;
}
return std::make_pair(min_factor, max_factor);
}
int main() {
std::cout << "Product of smallest and greatest prime factors of n for 1 to "
"100:\n";
for (unsigned int n = 1; n <= 100; ++n) {
auto p = min_max_prime_factors(n);
std::cout << std::setw(4) << p.first * p.second
<< (n % 10 == 0 ? '\n' : ' ');
}
}
- Output:
Product of smallest and greatest prime factors of n for 1 to 100: 1 4 9 4 25 6 49 4 9 10 121 6 169 14 15 4 289 6 361 10 21 22 529 6 25 26 9 14 841 10 961 4 33 34 35 6 1369 38 39 10 1681 14 1849 22 15 46 2209 6 49 10 51 26 2809 6 55 14 57 58 3481 10 3721 62 21 4 65 22 4489 34 69 14 5041 6 5329 74 15 38 77 26 6241 10 9 82 6889 14 85 86 87 22 7921 10 91 46 93 94 95 6 9409 14 33 10
CLU
sieve = proc (max: int) returns (sequence[int])
prime: array[bool] := array[bool]$fill(2,max-1,true)
p: int := 2
while p*p <= max do
for c: int in int$from_to_by(p*p, max, p) do
prime[c] := false
end
p := p + 1
end
primes: array[int] := array[int]$[]
for i: int in array[bool]$indexes(prime) do
if prime[i] then array[int]$addh(primes, i) end
end
return(sequence[int]$a2s(primes))
end sieve
factors = proc (primes: sequence[int], n: int) returns (sequence[int])
if n=1 then return(sequence[int]$[1]) end
fac: array[int] := array[int]$[]
for p: int in sequence[int]$elements(primes) do
if n // p = 0 then array[int]$addh(fac, p) end
end
return(sequence[int]$a2s(fac))
end factors
start_up = proc ()
MAX = 100
po: stream := stream$primary_output()
primes: sequence[int] := sieve(MAX)
for i: int in int$from_to(1, MAX) do
facs: sequence[int] := factors(primes, i)
prod: int := sequence[int]$bottom(facs) * sequence[int]$top(facs)
stream$putright(po, int$unparse(prod), 6)
if i//10 = 0 then stream$putl(po, "") end
end
end start_up
- Output:
1 4 9 4 25 6 49 4 9 10 121 6 169 14 15 4 289 6 361 10 21 22 529 6 25 26 9 14 841 10 961 4 33 34 35 6 1369 38 39 10 1681 14 1849 22 15 46 2209 6 49 10 51 26 2809 6 55 14 57 58 3481 10 3721 62 21 4 65 22 4489 34 69 14 5041 6 5329 74 15 38 77 26 6241 10 9 82 6889 14 85 86 87 22 7921 10 91 46 93 94 95 6 9409 14 33 10
Factor
USING: grouping math math.primes.factors math.statistics
prettyprint ranges sequences ;
2 100 [a..b] [ factors minmax * ] map 1 prefix 10 group simple-table.
- Output:
1 4 9 4 25 6 49 4 9 10 121 6 169 14 15 4 289 6 361 10 21 22 529 6 25 26 9 14 841 10 961 4 33 34 35 6 1369 38 39 10 1681 14 1849 22 15 46 2209 6 49 10 51 26 2809 6 55 14 57 58 3481 10 3721 62 21 4 65 22 4489 34 69 14 5041 6 5329 74 15 38 77 26 6241 10 9 82 6889 14 85 86 87 22 7921 10 91 46 93 94 95 6 9409 14 33 10
FreeBASIC
Const maxNumber = 100 ' maximum number we will consider
' sieve the primes to maxNumber
Dim As Boolean prime(0 To maxNumber)
prime(0) = False
prime(1) = False
prime(2) = True
Dim As Integer i, j, s, ub = Ubound(prime)
For i = 3 To ub Step 2
prime(i) = True
Next i
For i = 4 To ub Step 2
prime(i) = False
Next
For i = 3 To Abs(Sqr(ub)) Step 2
If prime(i) Then
For s = i * i To ub Step i + i
prime(s) = False
Next s
End If
Next i
' construct tables of the minimum and maximum prime factors
' of numbers up to max number
Dim As Integer minPF(1 To maxNumber)
For i = 1 To Ubound(minPF)
minPF(i) = 0
Next i
Dim As Integer maxPF(1 To maxNumber)
For i = 1 To Ubound(minPF)
maxPF(i) = 0
Next i
minPF(1) = 1
maxPF(1) = 1
For i = 1 To maxNumber
If prime(i) Then
For j = i To Ubound(minPF) Step i
If minPF(j) = 0 Then minPF(j) = i
maxPF(j) = i
Next j
End If
Next i
' print the products of the min and max prime factors
For i = 1 To maxNumber
Print Using "#####"; minPF(i) * maxPF(i);
If i Mod 10 = 0 Then Print
Next i
- Output:
Same as ALGOL 68 entry.
Go
package main
import (
"fmt"
"rcu"
)
func main() {
prods := make([]int, 100)
prods[0] = 1
for i := 2; i <= 100; i++ {
factors := rcu.PrimeFactors(i)
prods[i-1] = factors[0] * factors[len(factors)-1]
}
fmt.Println("Product of smallest and greatest prime factors of n for 1 to 100:")
rcu.PrintTable(prods, 10, 4, false)
}
- Output:
Product of smallest and greatest prime factors of n for 1 to 100: 1 4 9 4 25 6 49 4 9 10 121 6 169 14 15 4 289 6 361 10 21 22 529 6 25 26 9 14 841 10 961 4 33 34 35 6 1369 38 39 10 1681 14 1849 22 15 46 2209 6 49 10 51 26 2809 6 55 14 57 58 3481 10 3721 62 21 4 65 22 4489 34 69 14 5041 6 5329 74 15 38 77 26 6241 10 9 82 6889 14 85 86 87 22 7921 10 91 46 93 94 95 6 9409 14 33 10
J
1>.(>./*<./)@q:"0 >:i.10 10
1 4 9 4 25 6 49 4 9 10
121 6 169 14 15 4 289 6 361 10
21 22 529 6 25 26 9 14 841 10
961 4 33 34 35 6 1369 38 39 10
1681 14 1849 22 15 46 2209 6 49 10
51 26 2809 6 55 14 57 58 3481 10
3721 62 21 4 65 22 4489 34 69 14
5041 6 5329 74 15 38 77 26 6241 10
9 82 6889 14 85 86 87 22 7921 10
91 46 93 94 95 6 9409 14 33 10
jq
The following program will also work with gojq if the def of `_nwise/2` is uncommented.
# Uncomment for gojq
# def _nwise($n):
# def nw: if length <= $n then . else .[0:$n] , (.[$n:] | nw) end;
# nw;
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;
# Input: an integer
def isPrime:
. as $n
| if ($n < 2) then false
elif ($n % 2 == 0) then $n == 2
elif ($n % 3 == 0) then $n == 3
else 5
| until( . <= 0;
if .*. > $n then -1
elif ($n % . == 0) then 0
else . + 2
| if ($n % . == 0) then 0
else . + 4
end
end)
| . == -1
end;
# Input: an integer
# Output: a stream of the prime divisors of the input, in order
def prime_divisors:
. as $n
| if . < 2 then empty
elif . == 2 then 2
else (select(. % 2 == 0) | 2),
(range(3; ($n / 2) + 1; 2) | select( ($n % . == 0) and isPrime)),
($n | select(isPrime))
end;
def greatest_prime_divisor:
def odd: if . % 2 == 1 then . else . + 1 end;
. as $n
| if . < 2 then empty
elif . == 2 then 2
else first(
($n | select(isPrime)),
((( (($n|odd) - 1) / 2) | odd) as $odd
| range( $odd; 2; -2) | select( ($n % . == 0) and isPrime)),
(select(. % 2 == 0) | 2) )
end;
# Output: a stream of the products
def productMinMaxPrimeFactors:
1,
(range(2; infinite)
| [ first(prime_divisors), greatest_prime_divisor] | .[0] * .[-1]);
"Product of the smallest and greatest prime factors of n for 1 to 100:",
([limit(100; productMinMaxPrimeFactors)]
| _nwise(10) | map(lpad(4)) | join(" "))
Invocation jq -nr -f product-of-min-and-max-prime-factors.jq
- Output:
Product of the smallest and greatest prime factors of n for 1 to 100: 1 4 9 4 25 6 49 4 9 10 121 6 169 14 15 4 289 6 361 10 21 22 529 6 25 26 9 14 841 10 961 4 33 34 35 6 1369 38 39 10 1681 14 1849 22 15 46 2209 6 49 10 51 26 2809 6 55 14 57 58 3481 10 3721 62 21 4 65 22 4489 34 69 14 5041 6 5329 74 15 38 77 26 6241 10 9 82 6889 14 85 86 87 22 7921 10 91 46 93 94 95 6 9409 14 33 10
Julia
using Primes
function firstlastprimeprod(number_wanted)
for num in 1:number_wanted
fac = collect(factor(num))
product = isempty(fac) ? 1 : fac[begin][begin] * fac[end][begin]
print(rpad(product, 6), num % 10 == 0 ? "\n" : "")
end
end
firstlastprimeprod(100)
- Output:
1 4 9 4 25 6 49 4 9 10 121 6 169 14 15 4 289 6 361 10 21 22 529 6 25 26 9 14 841 10 961 4 33 34 35 6 1369 38 39 10 1681 14 1849 22 15 46 2209 6 49 10 51 26 2809 6 55 14 57 58 3481 10 3721 62 21 4 65 22 4489 34 69 14 5041 6 5329 74 15 38 77 26 6241 10 9 82 6889 14 85 86 87 22 7921 10 91 46 93 94 95 6 9409 14 33 10
Perl
use v5.36;
use ntheory 'factor';
use List::Util <min max>;
sub table ($c, @V) { my $t = $c * (my $w = 2 + length max @V); ( sprintf( ('%'.$w.'d')x@V, @V) ) =~ s/.{1,$t}\K/\n/gr }
my @p = 1;
for (2..100) {
my @f = factor $_;
push @p, min(@f) * max(@f);
}
say "Product of smallest and greatest prime factors of n for 1 to 100:\n" . table 10, @p;
- Output:
Product of smallest and greatest prime factors of n for 1 to 100: 1 4 9 4 25 6 49 4 9 10 121 6 169 14 15 4 289 6 361 10 21 22 529 6 25 26 9 14 841 10 961 4 33 34 35 6 1369 38 39 10 1681 14 1849 22 15 46 2209 6 49 10 51 26 2809 6 55 14 57 58 3481 10 3721 62 21 4 65 22 4489 34 69 14 5041 6 5329 74 15 38 77 26 6241 10 9 82 6889 14 85 86 87 22 7921 10 91 46 93 94 95 6 9409 14 33 10
Phix
with javascript_semantics sequence prods = repeat(0,100) for i=1 to 100 do sequence f = prime_factors(i,true) prods[i] = f[1] * f[$] end for printf(1,"Product of smallest and greatest prime factors of n for 1 to 100:\n%s\n", {join_by(prods,1,10," ",fmt:="%5d")})
- Output:
Product of smallest and greatest prime factors of n for 1 to 100: 1 4 9 4 25 6 49 4 9 10 121 6 169 14 15 4 289 6 361 10 21 22 529 6 25 26 9 14 841 10 961 4 33 34 35 6 1369 38 39 10 1681 14 1849 22 15 46 2209 6 49 10 51 26 2809 6 55 14 57 58 3481 10 3721 62 21 4 65 22 4489 34 69 14 5041 6 5329 74 15 38 77 26 6241 10 9 82 6889 14 85 86 87 22 7921 10 91 46 93 94 95 6 9409 14 33 10
PL/M
... under CP/M (or an emulator)
100H: /* FIND THE PRODUCT OF THE MIN AND MAX PRIME FACTORS OF SOME NUMBERS */
DECLARE FALSE LITERALLY '0', TRUE LITERALLY '0FFH';
/* CP/M SYSTEM CALL AND I/O ROUTINES */
BDOS: PROCEDURE( FN, ARG ); DECLARE FN BYTE, ARG ADDRESS; GOTO 5; END;
PR$CHAR: PROCEDURE( C ); DECLARE C BYTE; CALL BDOS( 2, C ); END;
PR$STRING: PROCEDURE( S ); DECLARE S ADDRESS; CALL BDOS( 9, S ); END;
PR$NL: PROCEDURE; CALL PR$CHAR( 0DH ); CALL PR$CHAR( 0AH ); END;
PR$NUMBER: PROCEDURE( N ); /* PRINTS A NUMBER IN THE MINIMUN FIELD WIDTH */
DECLARE N ADDRESS;
DECLARE V ADDRESS, N$STR ( 6 )BYTE, W BYTE;
V = N;
W = LAST( N$STR );
N$STR( W ) = '$';
N$STR( W := W - 1 ) = '0' + ( V MOD 10 );
DO WHILE( ( V := V / 10 ) > 0 );
N$STR( W := W - 1 ) = '0' + ( V MOD 10 );
END;
CALL PR$STRING( .N$STR( W ) );
END PR$NUMBER;
/* END SYSTEM CALL AND I/O ROUTINES */
DECLARE MAX$N LITERALLY '100', /* MAXIMUM NUMBER TO CONSIDER */
MAX$N$PLUS$1 LITERALLY '101'; /* MAX$N + 1 FOR ARRAY BOUNDS */
/* SIEVE THE PRIMES TO MAX$N */
DECLARE PRIME ( MAX$N$PLUS$1 )BYTE;
DO;
DECLARE ( I, S ) ADDRESS;
PRIME( 0 ), PRIME( 1 ) = FALSE;
PRIME( 2 ) = TRUE;
DO I = 3 TO LAST( PRIME ) BY 2; PRIME( I ) = TRUE; END;
DO I = 4 TO LAST( PRIME ) BY 2; PRIME( I ) = FALSE; END;
DO I = 3 TO LAST( PRIME ) / 2 BY 2;
IF PRIME( I ) THEN DO;
DO S = I + I TO LAST( PRIME ) BY I; PRIME( S ) = FALSE; END;
END;
END;
END;
/* CONSTRUCT TABLES OF THE MINIMUM AND MAXIMUM PRIME FACTORS OF NUMBERS */
/* UP TO MAX$N */
DECLARE ( MIN$PF, MAX$PF ) ( MAX$N$PLUS$1 )ADDRESS;
DECLARE ( I, J ) BYTE;
DECLARE PRODUCT ADDRESS;
DO I = 1 TO LAST( MIN$PF );
MIN$PF( I ), MAX$PF( I ) = 0;
END;
MIN$PF( 1 ) = 1;
MAX$PF( 1 ) = 1;
DO I = 1 TO MAX$N;
IF PRIME( I ) THEN DO;
DO J = I TO MAX$N BY I;
IF MIN$PF( J ) = 0 THEN MIN$PF( J ) = I;
MAX$PF( J ) = I;
END;
END;
END;
/* PRINT THE PRODUCTS OF THE MIN AND MAX PRIME FACTORS */
DO I = 1 TO MAX$N;
PRODUCT = MIN$PF( I ) * MAX$PF( I );
IF PRODUCT < 10 THEN CALL PR$CHAR( ' ' );
IF PRODUCT < 100 THEN CALL PR$CHAR( ' ' );
IF PRODUCT < 1000 THEN CALL PR$CHAR( ' ' );
CALL PR$CHAR( ' ' );
CALL PR$NUMBER( PRODUCT );
IF I MOD 10 = 0 THEN CALL PR$NL;
END;
EOF
- Output:
1 4 9 4 25 6 49 4 9 10 121 6 169 14 15 4 289 6 361 10 21 22 529 6 25 26 9 14 841 10 961 4 33 34 35 6 1369 38 39 10 1681 14 1849 22 15 46 2209 6 49 10 51 26 2809 6 55 14 57 58 3481 10 3721 62 21 4 65 22 4489 34 69 14 5041 6 5329 74 15 38 77 26 6241 10 9 82 6889 14 85 86 87 22 7921 10 91 46 93 94 95 6 9409 14 33 10
Python
''' Rosetta code rosettacode.org/wiki/Product_of_min_and_max_prime_factors '''
from sympy import factorint
NUM_WANTED = 100
for num in range(1, NUM_WANTED + 1):
fac = factorint(num, multiple=True)
product = fac[0] * fac[-1] if len(fac) > 0 else 1
print(f'{product:5}', end='\n' if num % 10 == 0 else '')
- Output:
1 4 9 4 25 6 49 4 9 10 121 6 169 14 15 4 289 6 361 10 21 22 529 6 25 26 9 14 841 10 961 4 33 34 35 6 1369 38 39 10 1681 14 1849 22 15 46 2209 6 49 10 51 26 2809 6 55 14 57 58 3481 10 3721 62 21 4 65 22 4489 34 69 14 5041 6 5329 74 15 38 77 26 6241 10 9 82 6889 14 85 86 87 22 7921 10 91 46 93 94 95 6 9409 14 33 10
Raku
use Prime::Factor;
put "Product of smallest and greatest prime factors of n for 1 to 100:\n" ~
(1..100).map({ 1 max .max × .min given cache .&prime-factors })».fmt("%4d").batch(10).join: "\n";
- Output:
Product of smallest and greatest prime factors of n for 1 to 100: 1 4 9 4 25 6 49 4 9 10 121 6 169 14 15 4 289 6 361 10 21 22 529 6 25 26 9 14 841 10 961 4 33 34 35 6 1369 38 39 10 1681 14 1849 22 15 46 2209 6 49 10 51 26 2809 6 55 14 57 58 3481 10 3721 62 21 4 65 22 4489 34 69 14 5041 6 5329 74 15 38 77 26 6241 10 9 82 6889 14 85 86 87 22 7921 10 91 46 93 94 95 6 9409 14 33 10
Wren
import "./math" for Int
import "./fmt" for Fmt
var prods = List.filled(100, 0)
prods[0] = 1
for (i in 2..100) {
var factors = Int.primeFactors(i)
prods[i-1] = factors[0] * factors[-1]
}
System.print("Product of smallest and greatest prime factors of n for 1 to 100:")
Fmt.tprint("$4d", prods, 10)
- Output:
Product of smallest and greatest prime factors of n for 1 to 100: 1 4 9 4 25 6 49 4 9 10 121 6 169 14 15 4 289 6 361 10 21 22 529 6 25 26 9 14 841 10 961 4 33 34 35 6 1369 38 39 10 1681 14 1849 22 15 46 2209 6 49 10 51 26 2809 6 55 14 57 58 3481 10 3721 62 21 4 65 22 4489 34 69 14 5041 6 5329 74 15 38 77 26 6241 10 9 82 6889 14 85 86 87 22 7921 10 91 46 93 94 95 6 9409 14 33 10
XPL0
func MinMaxPrimeFactors(N);
int N, Min, Max, P; \(Min and Max must be in order shown)
[Min:= 1; Max:= 1;
if (N&1) = 0 then
[while (N&1) = 0 do
N:= N>>1;
Min:= 2;
Max:= 2;
];
P:= 3;
while P*P <= N do
[if rem(N/P) = 0 then
[while rem(N/P) = 0 do
N:= N/P;
if Min = 1 then
Min:= P;
Max:= P;
];
P:= P+2;
];
if N > 1 then
[if Min = 1 then
Min:= N;
Max:= N;
];
return @Min; \risky
];
int N, P;
[Text(0, "Product of smallest and greatest prime factors of N for 1 to 100:^m^j");
Format(5, 0);
for N:= 1 to 100 do
[P:= MinMaxPrimeFactors(N);
RlOut(0, float(P(0)*P(1)));
if rem(N/10) = 0 then CrLf(0);
]
]
- Output:
Product of smallest and greatest prime factors of N for 1 to 100: 1 4 9 4 25 6 49 4 9 10 121 6 169 14 15 4 289 6 361 10 21 22 529 6 25 26 9 14 841 10 961 4 33 34 35 6 1369 38 39 10 1681 14 1849 22 15 46 2209 6 49 10 51 26 2809 6 55 14 57 58 3481 10 3721 62 21 4 65 22 4489 34 69 14 5041 6 5329 74 15 38 77 26 6241 10 9 82 6889 14 85 86 87 22 7921 10 91 46 93 94 95 6 9409 14 33 10