Некоторое время назад я взглянул на основную факторизацию 27000:

27000 = 2 ³ × 3 ³ × 5 ³

В этом есть две особые вещи:

• последовательное простое число : простые числа последовательные: 2 - это первое простое число, 3 - второе простое число, 5 - третье простое число.
• показатель постоянной : показатель степени одинаков для каждого простого числа (всегда 3)

Математически выражено:

Целое число х является последовательно-простое число / с постоянным показателем , если существуют строго положительные целые числа п , к , м такой , что х = р _п ^м × р _{п + 1} ^м × ... × р _{п + к} ^м , где р _j - это j-е простое число

Ваша задача - проверить, удовлетворяет ли положительное целое число этим условиям.

Входные данные:

Целое положительное число> 1 в любой разумной форме.

Выход:

Одно из двух значений, по крайней мере, одно из которых должно быть постоянным, указывая, является ли входное число последовательным простым / постоянным показателем степени.

Краевые случаи:

• простые числа являются truthy, так как разложение для простого р является р ^-
• другие числа, которые можно записать как p ^m, где p - простое число, также верны.

Правила:

• Применяются стандартные лазейки.
• Не беспокойтесь о целочисленном переполнении, но числа до 255 должны работать.
• Самый короткий код в байтах побеждает.

Тестовые случаи:

Truthy:

2
3
4
5
6
7
8
9
11
13
15
27000
456533

Falsy:

10
12
14
72
10000000

Вот скрипт Python, генерирующий несколько тестовых случаев.

Тот факт, что я принял ответ, не означает, что вызов окончен; победитель еще может измениться!

05AB1E , 4 байта

Ó0ÛË

Попробуйте онлайн!

объяснение

Ó     # get a list of prime exponents
 0Û   # remove leading zeroes
   Ë  # all remaining elements are equal

Regex (ECMAScript), 276 205 201 193 189 байт

Сравнение кратностей (показателей степени) различных простых факторов представляет собой интересную проблему для решения с помощью регулярного выражения ECMAScript - отсутствие обратных ссылок, сохраняющихся в течение итераций цикла, затрудняет подсчет чего-либо. Даже если подсчет рассматриваемой числовой черты возможен, часто более косвенный подход делает гольф лучше.

Как и в других моих статьях по регулярному выражению в ECMA, я дам предупреждение: я настоятельно рекомендую научиться решать унарные математические задачи в регулярном выражении в ECMAScript. Для меня это было увлекательное путешествие, и я не хочу испортить его тем, кто потенциально может попробовать его сами, особенно тем, кто интересуется теорией чисел. См. Этот более ранний пост для списка последовательно рекомендованных спойлером рекомендованных проблем, чтобы решить одну за другой.

Так что не читайте дальше, если вы не хотите, чтобы какая-то продвинутая магия унарных регулярных выражений была испорчена для вас . Если вы действительно хотите сами разобраться в этой магии, я настоятельно рекомендую начать с решения некоторых проблем в регулярном выражении ECMAScript, как описано в этом посте, связанном выше.

Основная полезная нагрузка от ранее разработанного мной регулярного выражения оказалась очень подходящей для этой задачи. Это регулярное выражение, которое находит простые числа наибольшей кратности . Мое первое решение для этого было очень долгим, и позже я постепенно продвинулся вперед, сначала переписав его, чтобы использовать молекулярный взгляд , а затем перенес его обратно на простой ECMAScript, используя продвинутую технику, чтобы обойти отсутствие молекулярного взгляда , и впоследствии игра в гольф будет намного меньше, чем оригинальное простое решение ECMAScript.

Часть из этого регулярного выражения, которая относится к этой проблеме, является первым шагом, который находит Q, наименьший фактор из N, который разделяет все его основные факторы. Как только мы получим это число, все, что нам нужно сделать, чтобы показать, что N - «число с постоянной экспонентой», - это делить N на Q, пока мы не сможем больше; если результат равен 1, все простые числа имеют одинаковую кратность.

Отправив ответ, используя мой ранее разработанный алгоритм поиска Q, я понял, что его можно рассчитать совершенно по-другому: найти наибольший множитель без квадратов для N (используя тот же алгоритм, что и для регулярного выражения моего числа Кармайкла ). Как выясняется, это вовсе не представляет никаких трудностей * с точки зрения обхода отсутствия молекулярного предвзятого взгляда и заднего вида переменной длины (нет необходимости использовать продвинутый ранее метод) и на 64 байта короче! Кроме того, это исключает сложность обработки N без квадратов и простых N как различных особых случаев, исключая еще 7 байтов из этого решения.

(По-прежнему существуют другие проблемы, которые требуют использования продвинутой техники, ранее использовавшейся здесь, для упрощения вычисления Q, но в настоящее время ни одна из них не представлена ​​в моих сообщениях PPCG.)

Я поставил тест множественности перед тестом последовательных простых чисел, потому что последний намного медленнее; размещение тестов, которые могут быстрее провалиться, сначала ускоряет регулярные выражения для равномерно распределенного ввода. Гольф также лучше поставить первым, потому что он использует больше обратных ссылок (что стоило бы больше, если бы они были двузначными).

Мне удалось отбросить 4 байта из этого регулярного выражения (193 → 189), используя трюк, найденный Грими, который может дополнительно сократить деление в случае, когда коэффициент гарантированно будет больше или равен делителю.

^(?=(|(x+)\2*(?=\2$))((?=(xx+?)\4*$)(?=(x+)(\5+$))\6(?!\4*$))*x$)(?=.*$\2|((?=((x*)(?=\2\9+$)x)(\8*$))\10)*x$)(?!(((x+)(?=\13+$)(x+))(?!\12+$)(x+))\11*(?=\11$)(?!(\15\14?)?((xx+)\18+|x?)$))

Попробуйте онлайн!

# For the purposes of these comments, the input number = N.
^

# Assert that all of N's prime factors are of equal multiplicity
# Step 1: Find Q, the largest square-free factor of N (which will also be the smallest
# factor of N that has all the same prime factors as N) and put it in \2.
# If N is square-free, \2 will be unset.
(?=
    # Search through all factors of N, from largest to smallest, searching for one that
    # satisfies the desired property. The first factor tried will be N itself, for which
    # \2 will be unset.
    (|(x+)\2*(?=\2$))     # for factors < N: \2 = factor of N; tail = \2
    # Assert that tail is square-free (its prime factors all have single multiplicity)
    (
        (?=(xx+?)\4*$)    # \4 = smallest prime factor of tail
        (?=(x+)(\5+$))    # \5 = tail / \4 (implicitly); \6 = tool to make tail = \5
        \6                # tail = \5
        (?!\4*$)          # Assert that tail is no longer divisible by \4, i.e. that that
                          # prime factor was of exactly single multiplicity.
    )*x$
)
# Step 2: Require that either \2 is unset, or that the result of repeatedly
# dividing tail by \2 is 1.
(?=
    .*$\2
|
    (
        # In the following division calculation, we can skip the test for divisibility
        # by \2-1 because it's guaranteed that \2 <= \8. As a result, we did not need to
        # capture \2-1 above, and can use a better-golfed form of the division.
        (?=
            (              # \8 = tail / \2
                (x*)       # \9 = \8-1
                (?=\2\9+$)
                x
            )
            (\8*$)         # \10 = tool to make tail = \8
        )
        \10               # tail = \8
    )*
    x$                    # Require that the end result is 1
)

# Assert that there exists no trio of prime numbers such that N is divisible by the
# smallest and largest prime but not the middle prime.
(?!
    (                          # \11 = a factor of N
        (                      # \12 = a non-factor of N between \11 and \13
            (x+)(?=\13+$)      # \13 = a factor of N smaller than \11
            (x+)               # \14 = tool (with \15) to make tail = \13
        )
        (?!\12+$)
        (x+)                   # \15 = tool to make tail = \12
    )
    \11*(?=\11$)               # tail = \11

    # Assert that \11, \12, and \13 are all prime
    (?!
        (\15\14?)?             # tail = either \11, \12, or \13
        ((xx+)\18+|x?)$
    )
)

* Это все еще чище с молекулярным взглядом, без специального случая для N, являющегося свободным от квадратов. Это дает 6 байтов, в результате получается решение 195 187 183 байта :

^(?=(?*(x+))\1*(?=\1$)((?=(xx+?)\3*$)(?=(x+)(\4+$))\5(?!\3*$))*x$)(?=((?=((x*)(?=\1\8+$)x)(\7*$))\9)*x$)(?!(((x+)(?=\12+$)(x+))(?!\11+$)(x+))\10*(?=\10$)(?!(\14\13?)?((xx+)\17+|x?)$))

# For the purposes of these comments, the input number = N.
^

# Assert that all of N's prime factors are of equal multiplicity
# Step 1: Find Q, the largest square-free factor of N (which will also be the smallest
# factor of N that has all the same prime factors as N) and put it in \1.
(?=
    (?*(x+))              # \1 = proposed factor of N
    \1*(?=\1$)            # Assert that \1 is a factor of N; tail = \1
    # Assert that tail is square-free (its prime factors all have single multiplicity)
    (
        (?=(xx+?)\3*$)    # \3 = smallest prime factor of tail
        (?=(x+)(\4+$))    # \4 = tail / \3 (implicitly); \5 = tool to make tail = \4
        \5                # tail = \4
        (?!\3*$)          # Assert that tail is no longer divisible by \3, i.e. that that
                          # prime factor was of exactly single multiplicity.
    )*x$
)
# Step 2: Require that the result of repeatedly dividing tail by \1 is 1.
(?=
    (
        # In the following division calculation, we can skip the test for divisibility
        # by \1-1 because it's guaranteed that \2 <= \8. As a result, we did not need to
        # capture \1-1 above, and can use a better-golfed form of the division.
        (?=
            (             # \7 = tail / \1
                (x*)      # \8 = \7-1
                (?=\1\8+$)
                x
            )
            (\7*$)        # \9 = tool to make tail = \7
        )
        \9                # tail = \7
    )*
    x$                    # Require that the end result is 1
)

# Assert that there exists no trio of prime numbers such that N is divisible by the
# smallest and largest prime but not the middle prime.
(?!
    (                          # \10 = a factor of N
        (                      # \11 = a non-factor of N between \10 and \12
            (x+)(?=\12+$)      # \12 = a factor of N smaller than \10
            (x+)               # \13 = tool (with \14) to make tail = \12
        )
        (?!\11+$)
        (x+)                   # \14 = tool to make tail = \11
    )
    \10*(?=\10$)               # tail = \10

    # Assert that \10, \11, and \12 are all prime
    (?!
        (\14\13?)?             # tail = either \10, \11, or \12
        ((xx+)\17+|x?)$
    )
)

Здесь он перенесен в вид сзади переменной длины:

Regex (ECMAScript 2018), 198 195 194 186 182 байта

^(?=(x+)(?=\1*$)(?<=^x((?<!^\5*)\3(?<=(^\4+)(x+))(?<=^\5*(x+?x)))*))((?=((x*)(?=\1\8+$)x)(\7*$))\9)*x$(?<!(?!(\14\16?)?((xx+)\12+|x?)$)(?<=^\13+)((x+)(?<!^\15+)((x+)(?<=^\17+)(x+))))

Попробуйте онлайн!

# For the purposes of these comments, the input number = N.
^

# Assert that all of N's prime factors are of equal multiplicity
# Step 1: Find Q, the largest square-free factor of N (which will also be the smallest
# factor of N that has all the same prime factors as N) and put it in \1.
(?=
    (x+)(?=\1*$)      # \1 = factor of N; head = \1
    (?<=              # This is evaluated right-to-left, so please read bottom to top.
        ^x
        (
            (?<!^\5*)        # Assert that head is no longer divisible by \6, i.e. that
                             # that prime factor was of exactly single multiplicity.
            \3               # head = \4
            (?<=(^\4+)(x+))  # \4 = head / \5 (implicitly); \3 = tool to make head = \4
            (?<=^\5*(x+?x))  # \5 = smallest prime factor of head
        )*
    )
)
# Step 2: Require that the result of repeatedly dividing tail by \1 is 1.
(
    # In the following division calculation, we can skip the test for divisibility
    # by \1-1 because it's guaranteed that \2 <= \8. As a result, we did not need to
    # capture \1-1 above, and can use a better-golfed form of the division.
    (?=
        (             # \7 = tail / \1
            (x*)      # \8 = \7-1
            (?=\1\8+$)
            x
        )
        (\7*$)        # \9 = tool to make tail = \7
    )
    \9                # tail = \7
)*
x$                    # Require that the end result is 1

# Assert that there exists no trio of prime numbers such that N is divisible by the
# smallest and largest prime but not the middle prime.
# This is evaluated right-to-left, so please read bottom to top, but switch back to
# reading top to bottom at the negative lookahead.
(?<!
    # Assert that \13, \15, and \17 are all prime.
    (?!
        (\14\16?)?           # tail = either \13, \15, or \17
        ((xx+)\12+|x?)$
    )

    (?<=^\13+)
    (                        # tail = \13
        (x+)                 # \14 = tool to make tail = \15
        (?<!^\15+)
        (
            (x+)             # \16 = tool (with \14) to make tail = \17
            (?<=^\17+)(x+)   # \17 = a factor of N smaller than \13
        )                    # \15 = a non-factor of N between \13 and \17
    )                        # \13 = a factor of N
)

Желе , 13 6 5 байт

ÆEt0E

Попробуйте онлайн!

Все еще переиграл ... (спасибо Эрику за -1 байт)

объяснение

ÆE     # get a list of prime exponents (noooo long builtin name)
  t0   # remove zeroes on both sides (leading or trailing)
    E  # all remaining elements are equal

JavaScript (ES6), 87 байт

Возвращает 0 для истинности или ненулевое целое для ложных.

f=(n,k=2,j,i)=>n%k?j*(P=d=>k%--d?P(d):d==!i)(k)|j-i|(n>1&&f(n,k+1,j||i)):f(n/k,k,j,-~i)

Попробуйте онлайн!

комментарии

f = (                     // f() = recursive function taking:
  n,                      //   n = input
  k = 2,                  //   k = current factor
  j,                      //   j = reference exponent, initially undefined
  i                       //   i = current exponent, undefined each time we start testing
) =>                      //       the next factor
  n % k ?                 // if k is not a divisor of n:
    j * (                 //   ignore the primality of k if j is still undefined
      P = d =>            //     P() = function testing if k is prime:
        k % --d ?         //       decrement d; if d is not a divisor of k:
          P(d)            //         do a recursive call until it is
        :                 //       else:
          d == !i         //         unless i is already defined: d must not be equal to 1
                          //         (if it is: k is the next prime but does not divide n)
    )(k) |                //   initial call to P() with d = k
    j - i | (             //   if both i and j are defined, they must be equal
      n > 1 &&            //   if n is not yet equal to 1,
      f(n, k + 1, j || i) //   go on with k + 1; if j is undefined, set it to i
    )                     //   (otherwise, stop recursion and return what we have)
  :                       // else:
    f(n / k, k, j, -~i)   //   increment the current exponent and go on with n / k

CJam , 30 29 байт

{mFz~)-!\__W=,\0=>\-:mp1#W=&}

Попробуйте онлайн!

Мой первый ответ после почти 2 (!) - годичного перерыва, так что, вероятно, можно больше играть в гольф. Это блок, который принимает входные данные как целое число (может также отображаться для массивов целых чисел).

объяснение

{        e# Begin block
 mF      e# Factor input, giving an array of primes and their powers
 z~      e# Transpose and dump, giving an array of primes and an array of powers
 )-      e# Check that the powers are the same: subtract each power from the last element
 !       e# Negate to make sure they're all 0
 \__W=,  e# Get the range from 0 to the largest prime minus one
 \0=>    e# Slice that array so it only includes everything larger than the smallest prime
 \-      e# Remove the original primes from the range array
 :mp     e# Check each element for primality. If the input's primes are consecutive,
         e# this will contain no primes
 1#W=    e# Make sure a "1" is not found
 &       e# If the powers are the same AND primes are consecutive, return 1. Otherwise, 0.
}

Stax , 5 6 байт

╣♥qJ╬c

Запустите и отладьте его

Распакованный, размазанный и прокомментированный, это выглядит так.

|n    get the exponents of the prime factorization
0:D   trim leading zeroes
:u    array has exactly a single distinct element

Изменить: это не работает на 512. Я подумаю над этим и, надеюсь, исправлю позже. Это работает сейчас.

Stax , 9 байт

1 правдиво, 0 фальшиво

αAG<└\{┬⌠

Запустите и отладьте его

объяснение

|nX0-u%x:^=      # Full Program, unpacked, implicit input
|n               # Exponents of sequential primes in factorization. (eg. 20 -> [2 0 1])
  X              # Save to X register
   0-            # Remove all '0' from array
     u%          # Get unique numbers and get length of array
       x         # Copy back the array saved to X
        :^       # Is it ascending
         =       # Are the two comparisons equal? implicit output

Вероятно, можно больше играть в гольф, но это покрывает случаи, которые я пропустил в последнем решении.

MATL , 12 11 10 байт

YFtgYsg)Zs

Попробуйте это в MATL Online!

Спасибо Луису Мендо за часть удаления ведущих нулей. Он также указал, что обмен истинными значениями разрешен, поэтому он возвращает 0 для чисел, которые удовлетворяют требованиям вызова, и любое положительное значение в противном случае.

Grosso Modo, это генерирует показатели последовательной простой факторизации, удаляет начальные нули и вычисляет стандартное отклонение.

Java 10, 223 191 178 176 168 байт

n->{var s=new java.util.HashSet();for(int f=1,i=1,x,j;n>1;){for(x=++i,j=2;j<x;)x=x%j++<1?1:x;if(x>1){for(j=0;n%i<1&&n>(f=0);n/=i)j++;if(f<1)s.add(j);}}return s.size();}

Возвращается 1как правдивый и >=2как фальси.

Попробуйте онлайн.

Объяснение:

n->{                   // Method with integer parameter and boolean return-type
  var s=new java.util.HashSet();
                       //  Set to keep track of the prime exponents
  for(int f=1,         //  Prime-flag, starting at 1
          i=1,x,j;     //  Index and temp integers
          n>1;){       //  Loop as long as `n` is still larger than 1
    for(x=++i,         //   Set `x` to `i`, after we've increased `i` by 1 first with `++i`
        j=2;           //   Set `j` to 2 (first prime)
        j<x;)          //   Inner loop as long as `j` is still smaller than `x`
      x=x%j++<1?       //    If `x` is divisible by `j`:
         1             //     Set `x` to 1
        :              //    Else:
         x;            //     Leave `x` unchanged
    if(x>1){           //    If `x` is larger than 1 (if `i` is a prime):
      for(j=0;         //     Use `j` as counter, and set it to 0
          n%i<1        //     If `n` is divisible by `i`:
                       //      And loop as long as `n` is still divisible by `i`,
          &&n>         //      and `n` is larger than 0
              (f=0);   //      (and set `f` to 0 at the same time)
          n/=i)        //       Divide `n` by `i`
        j++;           //       And increase `j` by 1
      if(f<1)          //     If the flag `f` is now/still 0:
        s.add(j);}}    //      Add counter `j` to the Set
  return s.size();}    //  Return the amount of items in the Set
                       //  (1 being true, >=2 being false)

Некоторые примеры входов:

n=15:

• Флаг остается 1для первого простого 2 (потому что 15 не делится на 2).
• Флаг переходит от 1к, 0как только мы находимся на nвершине 3. Поскольку 15 делится на 3, становится 5 (15/3 ¹ ), и Сет становится [] → [1].
• Затем мы проверяем следующее простое число 5. Поскольку 5 делится на 5, nстановится 1 (5/5 ¹ ), а множество остается тем же ( [1] → [1]).
• Теперь n=1мы остановим внешний цикл. Set ( [1]) содержит только один элемент, 1из двух смежных простых чисел 3 и 5, поэтому мы возвращаем true.

n=14:

• Флаг идет от 1к 0для первого простого 2 (потому что 14 делится на 2). nстановится 7 (14/2 ¹ ), и Набор становится [] → [1].
• Затем мы проверяем следующее простое число 3. Поскольку 7 не делится на 3, nостается тем же самым, и множество становится [1] → [1,0].
• Затем мы проверяем следующее простое число 5. Поскольку 7 также не делится на 5, nостается тем же самым, и множество остается тем же самым ( [1,0] → [1,0]).
• Затем мы проверяем следующее простое число 7. Поскольку 7 делится на 7, nстановится 1 (7/7 ¹ ), и множество остается тем же ( [1,0] → [1,0]).
• Теперь n=1мы остановим внешний цикл. Set ( [1,0]) содержит два элемента, 1из несмежных простых чисел 2 и 7, и 0из простых чисел 3 и 5, поэтому мы возвращаем false.

n=72:

• Флаг идет от 1к 0для первого простого 2, потому что 72 делится на 2 (несколько раз). Так nстановится 9 (72/2 ³ ), и Набор становится [] → [3].
• Затем мы проверяем следующее простое число 3. Поскольку 9 делится на 3 (несколько раз), nстановится 1 (9/3 ² ), и множество становится [3] → [3,2].
• Теперь n=1мы остановим внешний цикл. Set ( [3,2]) содержит два элемента, 3из простого 2 и 2из простого 3, поэтому мы возвращаем false.

J , 16 байт

Большое спасибо FrownyFrog за -8 байт!

(=&#+/\=@#])_&q:

Попробуйте онлайн!

Мое старое решение:

J , 24 байта

[:(1=[:#@~.{.@I.}.])_&q:

Попробуйте онлайн!

Объяснение:

_&q: простые показатели

{.@I.}.] удаляет начальные нули, находя первый ненулевой элемент:

     }.   drop
       ]  from the list of exponents
{.@       as much items as the first of the 
   I.     indices of non-zero elements

1=[:#@~. проверяет, равны ли все остальные числа:

  [:#@~.  finds the length of the list after removing the duplicates
1=        is it 1?

Шелуха , 11 байт

Λ§*≈¤≈oṗ←gp

Попробуйте онлайн!

Выводит 0, если не число последовательных простых / постоянных экспонент.

MATL , 7 байт

0iYFhdz

Результат - 1если ввод удовлетворяет требованию.

Попробуйте онлайн! Или проверьте все тестовые случаи

объяснение

0    % Push 0
i    % Push input number
YF   % Exponents of consecutive prime factors
h    % Concatenate horizontally
d    % Consecutive differences
z    % Number of nonzeros. Implicitly display

Октава , 67 байт

@(x)~any(diff(find(h=histc(factor(x),primes(x))))-1)&h(h>0)==max(h)

Попробуйте онлайн!

Я считаю, что это единственное решение, которое использует гистограмму.

Объяснение:

Это создает гистограмму, где подсчитываемая переменная является факторами входных данных и помещается в ячейки primes(x), которые на все простые числа меньше входных. Затем мы находим расположение основных факторов, берем разницу между каждым из индексов и вычитаем один. Если есть какие-либо элементы, которые не равны нулю (т. Е. Разница индексов простых чисел не равна 1), то это приведет к ложному значению, в противном случае оно вернет истинное значение.

Затем мы проверяем, что все ненулевые элементы в гистограмме равны максимальному элементу. Если есть значения, которые не равны, то это приведет к ложному значению, в противном случае он вернет истинное значение.

Если оба эти блока являются правдивыми, то наш вход представляет собой последовательное число экспонент простого числа!

APL (Dyalog Extended) , 28 байт

{f p←`↓⍭⍵⋄(1=≢∪p)∧∨/f⍷⍸1⍭⍳⍵}

Попробуйте онлайн!

Как:

{f p←`↓⍭⍵⋄(1=≢∪p)∧∨/f⍷⍸1⍭⍳⍵} ⍝ Monadic function, takes an argument ⍵
       ⍭⍵                     ⍝ Prime factors and exponents of ⍵
     `↓                        ⍝ split the resulting matrix in 2 vectors
 f p←                          ⍝ assign the factors to f and the powers to p
         ⋄                     ⍝ then
                          ⍳⍵   ⍝ range [1..⍵]
                        1⍭     ⍝ primality check for each element in the vector
                       ⍸        ⍝ where; returns the indices of truthy values
                     f⍷         ⍝ find the factors; returns a boolean vector
                   ∨/           ⍝ logical OR reduction
                  ∧             ⍝ logical AND
           (   ∪p)              ⍝ unique members of the powers
              ≢                 ⍝ tally; returns the number of elements in the vector
            1=                  ⍝ check if there's only one element

Wolfram Language (Mathematica) , 65 байт

Differences[{PrimePi@#,#2}&@@@FactorInteger@#]~MatchQ~{{1,0}...}&

Попробуйте онлайн!

Par / GP , 63 байта

n->#Set(vector(#(a=factor(n)~),i,[primepi(a[1,i])-i,a[2,i]]))<2

Попробуйте онлайн!

J , 14 байт

1#.2~:/\0,_&q:

1 в выходных данных указывает последовательный показатель степени.

Попробуйте онлайн!

        0,_&q:   zero followed by the prime exponents of input
   2~:/\         for every two consecutive values, 1 if they are different
1#.              convert from base-1, just add them up

Чисто , 127 байт

import StdEnv
@n=[]== $n
?n#j= $n
= @n||j==filter@[hd j..last j]&&any(\p=(prod j)^p==n)[1..n]
$n=[i\\i<-[2..n-1]|n/i*i==n&& @i]

Попробуйте онлайн!

Определяет функцию, ? :: Int -> Boolиспользуемую $ :: Int -> [Int]для факторизации и @ :: Int -> Boolпроверки простоты.

APL (NARS) 41 символ, 82 байта

{(1=≢∪+/¨{v=⍵⊃v}¨⍳≢v)∧(1↓w)≡¯1↓1πw←∪v←π⍵}

{π⍵} - функция факторизации аргумента ⍵ в списке простых факторов (повторите, если одно простое число появляется больше времени);
{1π⍵} - функция, следующая за простым числом (обратите внимание, что в этом случае ее аргумент - не скаляр, а один массив целых чисел). тест:

  h←{(1=≢∪+/¨{v=⍵⊃v}¨⍳≢v)∧(1↓w)≡¯1↓1πw←∪v←π⍵}
  (2..30)/⍨h¨2..30
2 3 4 5 6 7 8 9 11 13 15 16 17 19 23 25 27 29 30 
  h¨27000 456533 72 10000000
1 1 0 0