Product of min and max prime factors: Difference between revisions
Content added Content deleted
(Added C++ solution) |
(Add Factor) |
||
| Line 121: | Line 121: | ||
9 82 6889 14 85 86 87 22 7921 10 |
9 82 6889 14 85 86 87 22 7921 10 |
||
91 46 93 94 95 6 9409 14 33 10 |
91 46 93 94 95 6 9409 14 33 10 |
||
</pre> |
|||
=={{header|Factor}}== |
|||
{{works with|Factor|0.99 2022-04-03}} |
|||
<syntaxhighlight lang=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.</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
</pre> |
||
Revision as of 05:55, 4 October 2022
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
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.
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
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