14
\$\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\$
3
  • 1
    \$\begingroup\$ Can n be 1? \$\endgroup\$ – user202729 Jun 20 '18 at 10:41
  • 1
    \$\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

36 Answers 36

1
2
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\$
1
0
\$\begingroup\$

Ruby, 26 bytes

->n,i=1{(1>n%i+=1)?i:redo}

Try it online!

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

QBasic, 39 bytes

INPUT x
p=2
WHILE x\p<x/p
p=p+1
WEND
?p

Trial division; finds the first factor greater than 1, which is guaranteed to be the prime factor.

The only trick here is the condition x\p<x/p, which uses integer vs. floating point division to test whether "x is not divisible by p." See this tip for details.

\$\endgroup\$
1
2

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.