Is it almost-prime?

Question

Sandbox

Definition: A positive integer n is almost-prime, if it can be written in the form n=p^k where p is a prime and k is also a positive integers. In other words, the prime factorization of n contains only the same number.

Input: A positive integer 2<=n<=2^31-1

Output: a truthy value, if n is almost-prime, and a falsy value, if not.

Truthy Test Cases:

2
3
4
8
9
16
25
27
32
49
64
81
1331
2401
4913
6859
279841
531441
1173481
7890481
40353607
7528289

Falsy Test Cases

6
12
36
54
1938
5814
175560
9999999
17294403

Please do not use standard loopholes. This is code-golf so the shortest answer in bytes wins!

Answer 1

Sagemath, 2 bytes

GF

Outputs via exception.

Try it online!

---

The Sagemath builtin \$\text{GF}\$ creates a Galois Field of order \$n\$. However, remember that \$\mathbb{F}_n\$ is only a field if \$n = p^k\$ where \$p\$ is a prime and \$k\$ a positive integer. Thus the function throws an exception if and only if its input is not a prime power.

Answer 2

Python 2, 42 bytes

f=lambda n,p=2:n%p and f(n,p+1)or p**n%n<1

Try it online!

Since Python doesn't have any built-ins for primes, we make do with checking divisibility.

We find the smallest prime p that's a factor of n by counting up p=2,3,4,... until n is divisible by p, that is n%p is zero. There, we check that this p is the only prime factor by checking that a high power of p is divisible by n. For this, p**n suffices.

As a program:

43 bytes

n=input()
p=2
while n%p:p+=1
print p**n%n<1

Try it online!

This could be shorter with exit codes if those are allowed.

46 bytes

lambda n:all(n%p for p in range(2,n)if p**n%n)

Try it online!

Answer 3

Shakespeare Programming Language, 329 bytes

,.Ajax,.Page,.Act I:.Scene I:.[Enter Ajax and Page]
Ajax:Listen tothy.
Page:You cat.
Scene V:.
Page:You is the sum ofYou a cat.
 Is the remainder of the quotient betweenI you nicer zero?If soLet usScene V.
Scene X:.
Page:You is the cube ofYou.Is you worse I?If soLet usScene X.
 You is the remainder of the quotient betweenYou I.Open heart

Try it online!

Outputs 0 if the input is almost prime, and a positive integer otherwise. I am not sure this is an acceptable output; changing it would cost a few bytes.

Explanation:

• Scene I: Page takes in input (call this n). Initialize Ajax = 1.
• Scene V: Increment Ajax until Ajax is a divisor of Page; call the final value p This gives the smallest divisor of Page, which is guaranteed to be a prime.
• Scene X: Cube Ajax until you end up with a power of p, say p^k which is greater than n. Then n is almost-prime iff n divides p^k.

Answer 4

MATL, 4 bytes

Yf&=

• For almost-primes the output is a matrix containing only 1s, which is truthy.
• Otherwise the output is a matrix containing several 1s and at least one 0, which is falsy.

Try it online! Or verify all test cases, including truthiness/falsihood test.

How it works

     % Implicit input
Yf   % Prime factors. Gives a vector with the possibly repeated prime factors
&=   % Matrix of all pair-wise equality comparisons
     % Implicit output

Answer 5

R, 36 32 29 bytes

-3 bytes by outputting a vector of booleans without extracting the first element

!(a=2:(n=scan()))[!n%%a]^n%%n

Try it online!

Outputs a vector of booleans. In R, a vector of booleans is truthy iff the first element is TRUE.

First, find the smallest divisor p of n. We can do this by checking all integers (not only primes), as the smallest divisor of an integer (apart from 1) is always a prime number. Here, let a be all the integers between 2 and n, then p=a[!n%%a][1] is the first element of a which divides n.

Then n is almost prime iff n divides p^n.

This fails for any moderately large input, so here is the previous version which works for most larger inputs:

R, 36 33 bytes

!log(n<-scan(),(a=2:n)[!n%%a])%%1

Try it online!

Compute the logarithm of n in base p: this is an integer iff n is almost prime.

This will fail due to floating point inaccuracy for certain (but far from all) large-ish inputs, in particular for one test case: \$4913=17^3\$.

Answer 6

C (gcc), 43 bytes

f(n,i){for(i=1;n%++i;);n=i<n&&f(n/i)^i?:i;}

Try it online!

Returns p if n is almost-prime, and 1 otherwise.

f(n,i){
    for(i=1;n%++i;);    // identify i = the least prime factor of n
    n=i<n&&f(n/i)^i     // if n is neither prime nor almost-prime
      ?                 //  return 1
      :i;               // return i
}

Answer 7

Wolfram Language (Mathematica), 11 bytes

PrimePowerQ

Try it online!

@Sisyphus saved 1 byte

Answer 8

05AB1E, 2 bytes

ÒË

Try it online!

Commented:

Ò   -- Are all the primes in the prime decomposition
 Ë  -- Equal?

Answer 9

J, ⁹ 8 bytes

1=#@=@q:

Try it online!

-1 byte thanks to xash

Tests if the self-classify = of the prime factors q: has length # equal to one 1=

Answer 10

APL (Dyalog Classic), 33 31 26 bytes

{⍵∊∊(((⊢~∘.×⍨)1↓⍳)⍵)∘*¨⍳⍵}

-5 bytes from Kevin Cruijssen's suggestion.

Warning: Very, very slow for larger numbers.

Explanation

{⍵∊∊(((⊢~∘.×⍨)1↓⍳)⍵)∘*¨⍳⍵} ⍵=n in all the following steps
                       ⍳⍵  range from 1 to n
                    ∘*¨    distribute power operator across left and right args
    (((⊢~∘.×⍨)1↓⍳)⍵)       list of primes till n
   ∊                       flatten the right arg(monadic ∊)
 ⍵∊                        is n present in the primes^(1..n)?

Try it online!

Answer 11

Pyth, 5 bytes

!t{PQ

Try it online!

Explanation:

Q - Takes integer input
P - List of prime factors
{ - Remove duplicate elements
t - Removes first element
! - Would return True if remaining list is empty, otherwise False

Answer 12

Setanta, 61 59 bytes

gniomh(n){p:=2nuair-a n%p p+=1nuair-a n>1 n/=p toradh n==1}

Try it here

Notes:

• The proper keyword is gníomh, but Setanta allows spelling it without the accents so I did so to shave off a byte.

Answer 13

Haskell, 36 bytes

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

Try it online!

36 bytes

f n=and[mod(gcd d n^n)n<2|d<-[1..n]]

Try it online!

39 bytes

f n=all((`elem`[1,n]).gcd n.(^n))[2..n]

Try it online!

39 bytes

f n=mod n(n-sum[1|1<-gcd n<$>[1..n]])<1

Try it online!

40 bytes

f n=and[mod(p^n)n<1|p<-[2..n],mod n p<1]

Try it online!

Answer 14

JavaScript (ES6), 43 bytes

Without BigInts

Returns a Boolean value.

f=(n,k=1)=>n%1?!~~n:f(n<0?n/k:n%++k?n:-n,k)

Try it online!

A recursive function that first looks for the smallest divisor \$k>1\$ of \$n\$ and then divides \$-n\$ by \$k\$ until it's not an integer anymore. (The only reason why we invert the sign of \$n\$ when \$k\$ is found is to distinguish between the two steps of the algorithm.)

If \$n\$ is almost-prime, the final result is \$-\dfrac{1}{k}>-1\$. So we end up with \$\lceil n\rceil=0\$.

If \$n\$ is not almost-prime, there exists some \$q>k\$ coprime with \$k\$ such that \$n=q\times k^{m}\$. In that case, the final result is \$-\dfrac{q}{k}<-1\$. So we end up with \$\lceil n\rceil<0\$.

---

JavaScript (ES11), 33 bytes

With BigInts

With BigInts, using @xnor's approach is probably the shortest way to go.

Returns a Boolean value.

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

Try it online!

Answer 15

Retina 0.8.2, 50 bytes

.+
$*
^(?=(11+?)\1*$)((?=\1+$)(?=(1+)(\3+)$)\4)+1$

Try it online! Link includes faster test cases. Based on @Deadcode's answer to Match strings whose length is a fourth power. Explanation:

.+
$*

Convert the input to unary.

^(?=(11+?)\1*$)

Start by matching the smallest factor \$ p \$ of \$ n \$. (\$ p \$ is necessarily prime, of course.)

(?=\1+$)(?=(1+)(\3+)$)

While \$ p | \frac n { p^i } \$, find \$ \frac n { p^i } \$'s largest proper factor, which is necessarily \$ \frac n { p^{i+1} } \$.

\4

The factorisation also captures \$ (p - 1) \frac n { p^{i+1} } \$, which is subtracted from \$ \frac n { p^i } \$, leaving \$ \frac n { p^{i+1} } \$ for the next pass through the loop.

(...)+1$

Repeat the division by \$ p \$ as many times as possible, then check that \$ \frac n { p^k } = 1 \$.

Answer 16

Io, 48 bytes

Port of @RobinRyder's R answer.

method(i,c :=2;while(i%c>0,c=c+1);i log(c)%1==0)

Try it online!

Explanation

method(i,            // Take an input
    c := 2           // Set counter to 2
    while(i%c>0,     // While the input doesn't divide counter:
        c=c+1        //     Increment counter
    )
    i log(c)%1==0    // Is the decimal part of input log counter equal to 0?
)

Answer 17

Assembly (MIPS, SPIM), 238 bytes, 6 * 23 = 138 assembled bytes

main:li$v0,5
syscall
move$t3,$v0
li$a0,0
li$t2,2
w:bgt$t2,$t3,d
div$t3,$t2
mfhi$t0
bnez$t0,e
add$a0,$a0,1
s:div$t3,$t2
mfhi$t0
bnez$t0,e
div$t3,$t3,$t2
b s
e:add$t2,$t2,1
b w
d:move$t0,$a0
li$a0,0
bne$t0,1,p
add$a0,$a0,1
p:li$v0,1
syscall

Try it online!

Answer 18

Brachylog, 2 bytes

Are all prime factors equal?

ḋ=

Try it online!

Answer 19

GAP 4.7, 31 bytes

n->Length(Set(FactorsInt(n)))<2

This is a lambda. For example, the statement

Filtered([2..81], n->Length(Set(FactorsInt(n)))<2 );

yields the list [ 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32, 37, 41, 43, 47, 49, 53, 59, 61, 64, 67, 71, 73, 79, 81 ].

Try it online!

Answer 20

MathGolf, 10 bytes

╒g¶mÉk╒#─╧

Port of @Razetime's APL (Dyalog Classic) answer, so make sure to upvote him as well!

Try it online.

Explanation:

╒           # Push a list in the range [1, (implicit) input-integer)
 g          # Filter it by:
  ¶         #  Check if it's a prime
   m        # Map each prime to,
    É       # using the following three operations:
     k╒     #  Push a list in the range [1, input-integer) again
       #    #  Take the current prime to the power of each value in this list
        ─   # After the map, flatten the list of lists
         ╧  # And check if this list contains the (implicit) input-integer
            # (after which the entire stack joined together is output implicitly)

Answer 21

Factor, 35 bytes

: f ( n -- ? ) factors all-equal? ;

Try it online!

Answer 22

Japt, 6 bytes

I feel like this should be 1 or 2 bytes shorter ...

k ä¶ ×

Try it - includes all test cases

Answer 23

Java, 69 (or 64?) bytes

n->{int c=0,t=1;for(;t++<n;)if(n%t<1)for(c++;n%t<1;)n/=t;return c<2;}

Try it online.

Explanation:

n->{                // Method with integer parameter and boolean return-type
  int c=0,          //  Counter-integer, starting at 0
  t=1;for(;t++<n;)  //  Loop `t` in the range (1,n]:
    if(n%t<1)       //   If the input is divisible by `t`:
      for(c++;      //    Increase the counter by 1
          n%t<1;)   //    Loop as long as the input is still divisible by `t`
        n/=t;       //     And divide `n` by `t` every iteration
  return c<2;}      //  Return whether the counter is 1

---

If we would be allowed to ignore floating point inaccuracies, a port of @RobinRyder's R answer would be 64 bytes instead:

n->{int m=1;for(;n%++m>0;);return Math.log(n)/Math.log(m)%1==0;}

Try it online.

Explanation:

n->{               // Method with integer parameter and boolean return-type
  int m=1;         //  Minimum divisor integer `m`, starting at 1
  for(;n%++m>0;);  //  Increase `m` by 1 before every iteration with `++m`
                   //  And continue looping until the input is divisible by `m`
  return Math.log(n)/Math.log(m)
                   //  Calculate log_m(n)
         %1==0;}   //  And return whether it has no decimal values after the comma

But unfortunately this approach fails for test case 4913 which would become 2.9999999999999996 instead of 3.0 due to floating point inaccuracies (it succeeds for all other test cases).
A potential fix would be 71 bytes:

n->{int m=1;for(;n%++m>0;);return(Math.log(n)/Math.log(m)+1e9)%1<1e-8;}

Try it online.

Answer 24

Jelly, 3 bytes

ÆfE

Try it online!

Answer 25

Burlesque, 6 bytes

rifCsm

Try it online!

Explanation:

ri      # Read integer from input
  fC    # Find its prime factorisation
    sm  # Are all values the same?