13
\$\begingroup\$

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 . Shortest answer in bytes wins.

\$\endgroup\$
  • 1
    \$\begingroup\$ Can n be 1? \$\endgroup\$ – user202729 Jun 20 '18 at 10:41
  • \$\begingroup\$ @user202729: In the 4th test-case n = 1. \$\endgroup\$ – Emigna Jun 20 '18 at 10:53
  • 15
    \$\begingroup\$ Maybe it would have been more challenging to get the power part instead of the prime part. As it is, this is just "Get the lowest factor that isn't 1" \$\endgroup\$ – Jo King Jun 20 '18 at 13:48

32 Answers 32

13
\$\begingroup\$

Shakespeare Programming Language, 209 207 bytes

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

Try it online!

(I/you)*you<I is shorter than I%you>0 in SPL.

\$\endgroup\$
  • 1
    \$\begingroup\$ The right tool for the job. \$\endgroup\$ – Jeremy Weirich Jun 20 '18 at 20:09
12
\$\begingroup\$

05AB1E, 1 byte

f

Try it online!

\$\endgroup\$
7
\$\begingroup\$

Java 8, 46 39 37 bytes

n->{int r=1;for(;n%++r>0;);return r;}

-7 bytes indirectly thanks to @Tsathoggua.
-2 bytes thanks to JoKing

Try it online.

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
\$\endgroup\$
  • \$\begingroup\$ Following Luis Mendo's answer in python3, would it be possible to write n->{for(int i=1;++i<=n;)if(n%i<1)return i;} to get 43 characters? (I don't speak Java.) \$\endgroup\$ – Tsathoggua Jun 20 '18 at 12:52
  • \$\begingroup\$ @Tsathoggua As you have it right now not, since Java methods must always have a return. 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\$ – Kevin Cruijssen Jun 20 '18 at 13:14
  • 1
    \$\begingroup\$ How about 37 bytes. I'm not familiar enough with Java to see if any more can be golfed \$\endgroup\$ – Jo King Jun 20 '18 at 13:30
  • \$\begingroup\$ @JoKing I don't see anything to golf further, so thanks for the -2. \$\endgroup\$ – Kevin Cruijssen Jun 20 '18 at 14:06
5
\$\begingroup\$

Python 3, 36 35 bytes

-1 byte thanks to mathmandan

f=lambda n,x=2:n%x and f(n,x+1)or x

Try it online!

Recursive function that finds the first factor larger than 1

\$\endgroup\$
  • 1
    \$\begingroup\$ Nice. You can (usually) save a byte if you replace if/else with and/or. Like, f=lambda n,x=2:n%x and f(n,x+1)or x. \$\endgroup\$ – mathmandan Jun 20 '18 at 16:51
4
\$\begingroup\$

MATL, 4 3 bytes

Yfu

Try it online!

Explanation:

       % Implicit input:      [59049]
Yf     % Prime factorization: [3 3 3 3 3 3 3 3 3 3]
  u    % Unique elements:     [3]
       % Implicit output
\$\endgroup\$
  • 1
    \$\begingroup\$ Very nice improvement! I would upvote again :-) \$\endgroup\$ – Luis Mendo Jun 20 '18 at 12:54
4
\$\begingroup\$

Whitespace, 80 61 60 bytes

[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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Do you need the i == n check? n%n would be 0 anyway \$\endgroup\$ – Jo King Jun 20 '18 at 11:03
  • \$\begingroup\$ @JoKing Ah, of course. Thanks, 19 bytes saved right there. :) \$\endgroup\$ – Kevin Cruijssen Jun 20 '18 at 11:07
  • \$\begingroup\$ Could you only loop if not n%i and call the print afterwards? \$\endgroup\$ – Jo King Jun 20 '18 at 11:12
  • 1
    \$\begingroup\$ @JoKing I'm pretty sure not. Whitespace doesn't really have loops, it just has jumps to labels. The only three options I have is to: 1. jump to a certain label unconditionally; 2. jump to a certain label if the top of the stack is 0; 3. jump to a certain label if the top of the stack is negative. Unfortunately there isn't a "jump to label if positive" to continue the loop. I could accomplish this by multiplying by -1 before checking for negative, but I doubt that will be shorter. \$\endgroup\$ – Kevin Cruijssen Jun 20 '18 at 11:15
  • 1
    \$\begingroup\$ Tried to do it with a negative modulus and ended up at <s>62</s>60 bytes (yay). Turns out you can't store at negative heap addresses (though 0 saved a couple of bytes) \$\endgroup\$ – Jo King Jun 20 '18 at 12:35
4
\$\begingroup\$

Octave, 16 bytes

@(x)factor(x)(1)

Try it online!

Explanation:

@(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
\$\endgroup\$
  • 1
    \$\begingroup\$ +1 for max factor \$\endgroup\$ – Brain Guider Jun 20 '18 at 16:48
3
\$\begingroup\$

Funky, 30 bytes

n=>fori=2n>i i++if1>n%i breaki

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 0== can be 1> I think. \$\endgroup\$ – Kevin Cruijssen Jun 20 '18 at 9:09
2
\$\begingroup\$

JavaScript (ES6), 25 bytes

f=(n,k=2)=>n%k?f(n,k+1):k

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Jelly, 3 bytes

ÆfḢ

Try it online!

ÆfṪ, ÆfX could also be seriously competing functions.
ÆfQ could be a seriously competing full program.

\$\endgroup\$
2
\$\begingroup\$

C (gcc), 28 bytes

f(k,p){for(p=1;k%++p;);k=p;}

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Forth (gforth), 34 bytes

: f 1 begin 1+ 2dup mod 0= until ;

Try it online!

Explanation

  1. Iterate integers starting from 2
  2. Stop and return when you find one that divides n with no remainder

Code Explanation

: 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
\$\endgroup\$
1
\$\begingroup\$

Pyth, 2 bytes

hP

Try it here!

\$\endgroup\$
1
\$\begingroup\$

Brachylog, 2 bytes

ḋh

Try it online!

Explanation

ḋ       Prime decomposition
 h      Head
\$\endgroup\$
1
\$\begingroup\$

J, 4 bytes

0{q:

Select { the first 0 of the prime factors q:

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Neim, 1 byte

𝐔

Try it online!

\$\endgroup\$
  • \$\begingroup\$ U+1D414 is one character, but in UTF-8 and UTF-16 this is represented by 4 bytes. \$\endgroup\$ – Ruud Helderman Jun 21 '18 at 11:06
  • 1
    \$\begingroup\$ @RuudHelderman Correct, but this isn't in UTF-8 nor UTF-16. \$\endgroup\$ – Okx Jun 21 '18 at 14:28
  • 1
    \$\begingroup\$ @RuudHelderman You may want to see Neim codepage. \$\endgroup\$ – JungHwan Min Jun 21 '18 at 16:09
  • \$\begingroup\$ @JungHwanMin Thanks; browsing Okx's earlier Neim submissions, I noticed my slightly ignorant reaction wasn't the first. Clever feature, but far from obvious; warrants explanation (as done here). Quoting code-golf tag info: "Unless the question is specified to be scored by characters, it is scored by bytes. If it doesn't specify a character encoding to use for scoring, answers which use Unicode code points outside 0 to 255 should state the encoding used." \$\endgroup\$ – Ruud Helderman Jun 21 '18 at 19:20
  • \$\begingroup\$ @RuudHelderman per meta consensus, if an answer does not specify an encoding, it defaults to the language's default encoding. If that doesn't exist, then it is UTF-8. In this case, Neim has a defined default encoding, so it is assumed to be the encoding of the answer, without the answerer having to explain as such. \$\endgroup\$ – JungHwan Min Jun 21 '18 at 22:06
1
\$\begingroup\$

Haskell, 26 bytes

f n=until((<1).mod n)(+1)2

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Mathematica, 17 bytes

Divisors[#][[2]]&

The second smallest divisor.

\$\endgroup\$
1
\$\begingroup\$

R, 32 26 bytes

@Giuseppe with different logic and a shorter solution:

(x=2:(n=scan()))[!n%%x][1]

Try it online!

Original:

numbers::primeFactors(scan())[1]

Try it online!

This is obviously a much superior port of the 05AB1E solution.

\$\endgroup\$
0
\$\begingroup\$

ARBLE, 19 bytes

index(factors(a),1)

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Japt -g, 1 byte

k

Try it here

\$\endgroup\$
0
\$\begingroup\$

PowerShell, 31 bytes

param($a)(2..$a|?{!($a%$_)})[0]

Try it online!

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.

\$\endgroup\$
0
\$\begingroup\$

Perl 6, 22 bytes

{grep($_%%*,2..$_)[0]}

Try it online!

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.

\$\endgroup\$
0
\$\begingroup\$

Visual Basic .NET (.NET Framework v4.5), 123 71 bytes

-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

Try it online!

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ You don't need the prime check at all. The smallest factor of a number (other than 1) is guaranteed to be a prime, otherwise there would be a smaller factor \$\endgroup\$ – Jo King Jun 20 '18 at 13:54
  • \$\begingroup\$ @JoKing D'oh! Of course, can't believe I missed that. Thanks! \$\endgroup\$ – Brian J Jun 20 '18 at 13:55
0
\$\begingroup\$

Haskell, 29 bytes

f y=[x|x<-[2..],mod y x<1]!!0

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Python 3, 47 45 44 bytes

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]

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ You have an extra space before the if, and the condition can be <1 \$\endgroup\$ – Jo King Jun 20 '18 at 10:31
  • 1
    \$\begingroup\$ You can save one byte by doing range(n) and incrementing i in place \$\endgroup\$ – Jo King Jun 20 '18 at 23:04
0
\$\begingroup\$

Pari/GP, 17 bytes

n->factor(n)[1,1]

Try it online!


Pari/GP, 17 bytes

n->divisors(n)[2]

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Ruby, 100 bytes

require"prime"
i=gets.to_i
Prime.each(i){|p|(1..i).each{|n|c=p**n==i
    puts p if c
    exit if c}}

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Stax, 3 bytes

|fh

Run and debug it

First element of prime factorization.

\$\endgroup\$
0
\$\begingroup\$

Julia 0.6, 25 bytes

n->[2:n;][n.%(2:n).<1][1]

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.