17
\$\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\$
    – DELETE_ME
    Commented Jun 20, 2018 at 10:41
  • 1
    \$\begingroup\$ @user202729: In the 4th test-case n = 1. \$\endgroup\$
    – Emigna
    Commented Jun 20, 2018 at 10:53
  • 19
    \$\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
    Commented Jun 20, 2018 at 13:48

39 Answers 39

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
  • \$\begingroup\$ -4 bytes \$\endgroup\$
    – MarcMush
    Commented Feb 24, 2021 at 14:57
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\$
0
\$\begingroup\$

Thunno 2, 1 byte

Ƒ

Try it online!

Unique prime factors built-in.

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

Desmos, 32 bytes

-17 bytes thanks to @Aiden Chow!

d=[2...n]
f(n)=d[mod(n,d)=0].min

Try it on Desmos!

Find the smallest factor (>1) of \$n\$.

Desmos, 49 bytes

p=[\sqrt[i]n\for i=[n...1]]
f(n)=p[\ceil(p)=p][1]

Explaination

Finds the smallest integer value of \$\sqrt[i]n\$ (\$i\in\mathbb Z\$)

In other words, make \$\sqrt[i]n\$ an integer with the greatest value of \$i\$

Try it on Desmos!

\$\endgroup\$
3
  • \$\begingroup\$ 32 bytes \$\endgroup\$
    – Aiden Chow
    Commented Aug 18, 2023 at 4:53
  • \$\begingroup\$ @AidenChow darn, i'm surprised i didn't think of that \$\endgroup\$
    – fwoosh
    Commented Aug 18, 2023 at 4:57
  • \$\begingroup\$ It's always helpful to check other peoples' answers :P \$\endgroup\$
    – Aiden Chow
    Commented Aug 18, 2023 at 5:50
0
\$\begingroup\$

ARBLE, 17 bytes

primefactors(n)/z

Try it online!

\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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