Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It only takes a minute to sign up.
Sign up to join this community
Definition: a prime power is a natural number that can be expressed in the form pn where p is a prime and n is a natural number.
Task: Given a prime power pn > 1, return the prime p.
Testcases:
input output
9 3
16 2
343 7
2687 2687
59049 3
Scoring: This is code-golf. Shortest answer in bytes wins.
[] around the number) is a valid output?
\$\endgroup\$
Jun 20, 2018 at 11:10
f = push list of prime factors (no duplicates)
\$\endgroup\$
T.Ajax,.Page,.Act I:.Scene I:.[Enter Ajax and Page]Ajax:Listen tothy!Page:You cat!Scene V:.Page:You be the sum ofyou a cat!Be the product ofthe quotient betweenI you you worse I?If soLet usScene V.Open heart
(I/you)*you<I is shorter than I%you>0 in SPL.
n->{int r=1;for(;n%++r>0;);return r;}
-7 bytes indirectly thanks to @Tsathoggua.
-2 bytes thanks to JoKing
Explanation:
n->{ // Method with integer as both parameter and return-type
int r=1; // Start the result-integer `r` at 1
for(;n%++r>0;); // Increase `r` by 1 before every iteration with `++r`
// and loop until `n` is divisible by `r`
return r;} // After the loop, return `r` as result
n->{for(int i=1;++i<=n;)if(n%i<1)return i;} to get 43 characters? (I don't speak Java.)
\$\endgroup\$
Jun 20, 2018 at 12:52
n->{for(int i=1;++i<=n;)if(n%i<1)return i;return n;} would work, but is unfortunately longer. Java can have a single return in infinite loops however, which does indeed save bytes, so thanks! n->{for(int i=1;;)if(n%++i<1)return i;}. Since i will become n eventually (like with the test case 2687) and n%n==0, the i<=n isn't required in this case.
\$\endgroup\$
Jun 20, 2018 at 13:14
-1 byte thanks to mathmandan
f=lambda n,x=2:n%x and f(n,x+1)or x
Recursive function that finds the first factor larger than 1
if/else with and/or. Like, f=lambda n,x=2:n%x and f(n,x+1)or x.
\$\endgroup\$
Jun 20, 2018 at 16:51
Yfu
% Implicit input: [59049]
Yf % Prime factorization: [3 3 3 3 3 3 3 3 3 3]
u % Unique elements: [3]
% Implicit output
[S S T T N
_Push_-1][S S S N
_Push_0][T N
T T _Read_STDIN_as_number][N
S S N
_Create_Label_LOOP][S S S T N
_Push_1][T S S T _Subtract][S N
S _Duplicate][S S S N
_Push_0][T T T _Retrieve][S N
T _Swap][T S T T _Modulo][N
T T N
_If_0_Jump_to_Label_LOOP][S S T T N
_Push_-1][T S S N
_Multiply][T N
S T _Print_as_number]
-20 bytes thanks to @JoKing.
Letters S (space), T (tab), and N (new-line) added as highlighting only.
[..._some_action] added as explanation only.
Try it online (with raw spaces, tabs and new-lines only).
Explanation in pseudo-code:
Integer n = STDIN as integer
Integer i = -1
Start LOOP:
i = i - 1
if(n modulo-i is negative)
Go to next iteration of LOOP
else
i = i * -1
Print i
Exit with error: No exit defined
Example run: input = 9
Command Explanation Stack Heap STDIN STDOUT STDERR
SSTTN Push -1 [-1]
SSSN Push 0 [-1,0]
TNTT Read STDIN as integer [-1] {0:9} 9
NSSN Create Label_LOOP [-1] {0:9}
SSSTN Push 1 [-1,1] {0:9}
TSST Subtract top two (-1-1) [-2] {0:9}
SNS Duplicate top (-2) [-2,-2] {0:9}
SSSN Push 0 [-2,-2,0] {0:9}
TTT Retrieve [-2,-2,9] {0:9}
SNT Swap top two [-2,9,-2] {0:9}
TSTT Modulo top two (9%-2) [-2,-1] {0:9}
NTSN If neg.: Jump to Label_LOOP [-2] {0:9}
SSTTN Push -1 [-2,-1] {0:9}
TSST Subtract top two (-2-1) [-3] {0:9}
SNS Duplicate top (-2) [-3,-3] {0:9}
SSSN Push 0 [-3,-3,0] {0:9}
TTT Retrieve [-3,-3,9] {0:9}
SNT Swap top two [-3,9,-3] {0:9}
TSTT Modulo top two (9%-3) [-3,0] {0:9}
NTSN If neg.: Jump to Label_LOOP [-3] {0:9}
SSTTN Push -1 [-3,-1] {0:9}
TSSN Multiply top two (-3*-1) [3] {0:9}
TNST Print as integer [] {0:9} 3
error
Program stops with an error: No exit found.
i == n check? n%n would be 0 anyway
\$\endgroup\$
n%i and call the print afterwards?
\$\endgroup\$
@(x)factor(x)(1)
@(x) % Anonymous function taking x as input
factor(x) % Prime factorization
(1) % Get the first element
Or:
@(x)max(factor(x)) % the makeup of makeup artists
ÆfḢ
ÆfṪ, ÆfX could also be seriously competing functions.
ÆfQ could be a seriously competing full program.
: f 1 begin 1+ 2dup mod 0= until ;
: f \ Define a new word
1 \ place a 1 on the stack (to use as a counter/index)
begin \ start indefinite loop
1+ 2dup \ increment counter and duplicate counter and prime power
mod \ calculate power % index
0= until \ end the loop if modulus is 0 (no remainder)
; \ end word definition
(xx+?)\1*$
Works by finding the smallest prime factor. Takes its input in bijective unary, as a sequence of x characters in which the length represents the number. The output is returned in capture group 1.
# No anchor needed, since every input N>=2 returns an output
(xx+?) # \1 = the smallest number >=2 for which:
\1*$ # N-\1 is divisible by \1
′
There was a builtin just for this.
h at the end.
\$\endgroup\$
′ gives all prime factors. The question only wants one (hence why I made it ′h). However, other answers seem to get away with printing all factors, so it's just ′ (or Ǐ)
\$\endgroup\$
Divisors[#][[2]]&
The second smallest divisor.
param($a)(2..$a|?{!($a%$_)})[0]
Constructs a range from 2 to input $a, pulls out those elements where (?) the modulo operation % results in a zero !(...) (i.e., those that are divisors of $a), and then takes the smallest [0] one thereof. That's left on the pipeline, output is implicit.
{grep($_%%*,2..$_)[0]}
Anonymous code block that filters the factors of the range of 2 to the input and returns the first one. I tried using ^$ to save 2 bytes, but that didn't work in the case that the input was prime.
-52 bytes thanks to @Jo King
Function A(n)
For i=n To 2 Step-1
A=If(n Mod i=0,i,A)
Next
End Function
Ungolfed:
Function A(input As Long) As Long
For i = input To 2 Step -1
A = If (input Mod i = 0, i, A)
Next
End Function
Explanation:
The i loop searches backwards from the first number, and finds all numbers that divide it evenly. Because we are going backwards, the smallest is stored in the vairable A.
VB gives you a free variable that matches your function name (in my case, A). At the end of the function execution, the value in that variable is returned (barring an explicit Return statement.
Inspired by Kevin Cruijssen's answer in Java.
2 3 bytes removed thanks to Jo King.
lambda n:[i+1for i in range(n)if n%-~i<1][1]
if, and the condition can be <1
\$\endgroup\$
range(n) and incrementing i in place
\$\endgroup\$
nbe 1? \$\endgroup\$n = 1. \$\endgroup\$