Для положительного целого числа nс простой факторизацией, n = p1^e1 * p2^e2 * ... pk^ekгде p1,...,pkпростые числа и e1,...,ekположительные целые, мы можем определить две функции:

Ω(n) = e1+e2+...+ekколичество простых делителей (посчитано с кратностью) ( A001222 )
- ω(n) = kчисло различных простых делителей. ( A001221 )

С помощью этих двух функций мы определяем избыток e(n) = Ω(n) - ω(n) ( A046660 ). Это можно рассматривать как меру того, насколько близко число к квадрату.

Вызов

Для заданного положительного целого числа nверните e(n).

Примеры

Для n = 12 = 2^2 * 3нас есть Ω(12) = 2+1и ω(12) = 2поэтому e(12) = Ω(12) - ω(12) = 1. Для любого квадратичного числа nмы, безусловно, имеем e(n) = 0. Первые несколько терминов

Еще некоторые подробности в вики OEIS.

code-golf sequence number-theory primes flawr
источник

1

Может быть, уточнить, что ^это власть

Луис Мендо

5

Это не обязательно, по моему мнению. Этот символ используется здесь и во всем Интернете, а также на многих калькуляторах и во многих языках программирования.

flawr

7

MATL , 7 5 байт

Yfd~s

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

объяснение

Yf    % Implicit input. Obtain prime factors, sorted and with repetitions
d     % Consecutive differences
~     % Logical negate: zeros become 1, nonzeros become 0
s     % Sum. Implicit display

Луис Мендо
источник

Я не знал, как factorработает в MATL, действительно круто =)

flawr

@flawr Вы имеете в виду YF(в 7-байтовой версии кода) или Yf(5-байтовой)? Последний как в MATLAB

Луис Мендо

1

Функция для показателей степени 5 байт теперь еще

умнее

6

Брахилог , 11 байт

$pPd:Pr:la-

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

объяснение

$pP            P is the list of prime factors of the Input
  Pd           Remove all duplicates in P
    :Pr        Construct the list [P, P minus duplicates]
       :la     Apply "length" to the two elements of that list
          -    Output is the subtraction of the first element by the second one

Fatalize
источник

6

Mathematica, 23 байта

PrimeOmega@#-PrimeNu@#&

Очень скучно. FactorIntegerуже занимает 13 байт, и я не вижу много, что можно сделать с оставшимися 10.

u54112
источник

4

Желе , 5 байт

ÆfI¬S

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

Проверьте все тестовые случаи.

Порт Луис Мендо ответ в MATL .

ÆfI¬S

Æf     Implicit input. Obtain prime factors, sorted and with repetitions
  I    Consecutive differences
   ¬   Logical negate: zeros become 1, nonzeros become 0
    S  Sum. Implicit display

Дрянная Монахиня
источник

Для предыдущего подхода, я ÆF’SṪбы сработал

Sp3000

@ Sp3000 Вы должны опубликовать это

Leaky Nun

@ LeakyNun Я пытался портировать его сам, но определение ¬меня смутило. Я не знал, что это векторизация

Луис Мендо

@LuisMendo Действительно, документы на желе грязные.

Утренняя монахиня

3

05AB1E , 6 байтов

Òg¹fg-

объяснение

Òg      # number of prime factors with duplicates
     -  # minus
  ¹fg   # number of prime factors without duplicates

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

Emigna
источник

3

J 11 10 байт

Сохранено 1 байт благодаря Ионе .

1#.1-~:@q:

alephalpha
источник

1

1#.1-~:@q:для 10 байтов. хорошая идея, используя ~:кстати.

Иона

2

Pyth, 7 байт

-lPQl{P

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

orlp
источник

2

C 74 байта

f(n,e,r,i){r=0;for(i=2;n>1;i++,r+=e?e-1:e)for(e=0;n%i<1;e++)n/=i;return r;}

Идео это!

Дрянная Монахиня
источник

2

Python 2, 57 56 байт

f=lambda n,k=2:n/k and[f(n,k+1),(n/k%k<1)+f(n/k)][n%k<1]

Спасибо @JonathanAllan за отыгрывание 1 байта!

Проверьте это на Ideone .

Деннис
источник

Ах, хорошо - вы можете сохранить байт с помощьюn/k%k<1

Джонатан Аллан

Правильно, n уже делится на k в этой точке. Благодарность!

Деннис

2

Haskell, 65 байт

(c%x)n|x>n=c|mod n x>0=c%(x+1)$n|y<-div n x=(c+0^mod y x)%x$y
0%2

Damien
источник

если это одна функция: кто является входной переменной? кто выход? спасибо ...

РосЛюП

(%) принимает 3 входные переменные: аккумулятор (c), целое число (x) и целое число (n). Он возвращает избыток (n), когда c установлен на 0, а x на 2. Таким образом (0% 2) - это частичная функция, которая принимает n и возвращает ее избыток

Дэмиен

2

05AB1E , 4 байта

Ò¥_O

Порт ответа @LuisMendo на MATL .

Попробуйте онлайн или проверьте первые 15 контрольных примеров .

Объяснение:

Ò       # Get all prime factors with duplicates from the (implicit) input
        # (automatically sorted from lowest to highest)
 ¥      # Get all deltas
  _     # Check if it's equal to 0 (0 becomes 1; everything else becomes 0)
   O    # Take the sum (and output implicitly)

Кевин Круйссен
источник

1

Python 2, 100 99 98 96 байт

n=input()
i=2
f=[]
while i<n:
 if n%i:i+=1
 else:n/=i;f+=i,
if-~n:f+=n,
print len(f)-len(set(f))

Большая часть кода занята гольф-версией этого SO-ответа , в котором хранятся основные факторы входных данных f. Затем мы просто используем набор манипуляций для расчета избыточных факторов.

Спасибо Leaky Nun за спасение 1 3 байтов!

медь
источник

1

Brachylog , 11 байт

$p@b:la:-a+

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

Проверьте все тестовые случаи. (Оболочка длиннее функции ...)

$p@b:la:-a+

$p            prime factorization
  @b          group blocks of equal elements
    :la       length of each
       :-a    each minus 1
          +   sum

Дрянная Монахиня
источник

1

СИЛОС , 113 байт

readIO
t=2
lbla
e=0
GOTO b
lblc
i/t
e+1
lblb
m=i
m%t
n=1
n-m
if n c
d=e
d/d
e-d
r+e
A=i
A-1
t+1
if A a
printInt r

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

Порт моего ответа в Си .

Дрянная Монахиня
источник

Так близко к победе над С :(

Рохан Джунджхунвала

1

Javascript (ES6), 53 51 46 байт

e=(n,i=2)=>i<n?n%i?e(n,i+1):e(n/=i,i)+!(n%i):0

Сохранено 5 байтов благодаря Нейлу

Пример:

e=(n,i=2)=>i<n?n%i?e(n,i+1):e(n/=i,i)+!(n%i):0

// computing e(n) for n in [1, 30]
for(var n = 1, list = []; n <= 30; n++) {
  list.push(e(n));
}
console.log(list.join(','));

Развернуть фрагмент

Arnauld
источник

1

Вы можете сохранить 5 байт путем вычисления rрекурсивно: f=(n,i=2)=>i<n?n%i?f(n,i+1):f(n/=i,i)+!(n%i):0.

Нил

1

Баш, 77 байт

IFS=$'\n '
f=(`factor $1`)
g=(`uniq<<<"${f[*]}"`)
echo $((${#f[*]}-${#g[*]}))

Полная программа, с вводом в $1 и выводом на стандартный вывод.

Мы IFSначинаем с новой строки, чтобы расширение было "${f[*]}"разделено новой строкой. Мы используем арифметическую подстановку, чтобы вывести разницу между количеством слов в разложении и результатом фильтрации uniq. Само число печатается как префикс factor, но оно также присутствует после фильтрации, поэтому вычитается в вычитании.

Тоби Спейт
источник

0

Python, (с симпатией) 66 байт

import sympy;lambda n:sum(x-1for x in sympy.factorint(n).values())

sympy.factorintвозвращает словарь с факторами в качестве ключей и их кратностями в качестве значений, поэтому сумма значений равна, Ω(n)а количество значений равно ω(n), поэтому сумма уменьшенных значений - это то, что нам нужно.

Джонатан Аллан
источник

0

CJam, 11 байт

ri_mf,\mF,-

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

объяснение

ri_         Get an integer from input and duplicate it
   mf,      Get the number of prime factors (with repetition)
      \     Swap top 2 elements on the stack
       mF,  Get the number of prime factors (with exponents)
          - Subtract

Бизнес Кот
источник

0

С, 158

#define G(a,b) if(a)goto b
#define R return
f(n,i,j,o,w){if(!n)R 0;o=w=i=j=0;a:i+=2;b:if(n%i==0){++j;G(n/=i,b);}o+=!!j;w+=j;i+=(i==2);j=0;G(i*i<n,a);R w-o;}

В начале есть инструкция goto ... даже если она длиннее вашей, она более читабельна и правильна [если я не считаю слишком большой ...] один язык, имеющий 10000 библиотечных функций, хуже, чем язык что с несколькими, 20 или 30 библиотечными функциями можно сделать все лучше [потому что мы не можем запомнить все эти функции]

#define F for
#define P printf

main(i,r)
{F(i=0; i<100; ++i)
   r=f(i,0,0,0,0),P("[%u|%u]",i,r);
 R  0;
}

/*
 158
 [0|0][1|0][2|0][3|0][4|1][5|0][6|0][7|0][8|2]
 [9|0][10|0][11|0][12|1][13|0][14|0][15|0][16|3]
 [17|0][18|0][19|0][20|1][21|0][22|0][23|0][24|2][25|1][26|0][27|0] [28|1]
 [29|0][30|0][31|0][32|4][33|0][34|0][35|0][36|1]
 [37|0][38|0][39|0][40|2][41|0]
 */

RosLuP
источник

0

GNU sed + coreutils, 55 байт

(включая +1 за -rфлаг)

s/^/factor /e
s/ ([^ ]+)(( \1)*)/\2/g
s/[^ ]//g
y/ /1/

Ввод в десятичном виде, по стандартному вводу; вывод в одинарный, на стандартный вывод.

объяснение

#!/bin/sed -rf

# factor the number
s/^/factor /e
# remove first of each number repeated 0 or more times
s/ ([^ ]+)(( \1)*)/\2/g
# count just the spaces
s/[^ ]//g
y/ /1/

Тоби Спейт
источник

0

APL (NARS) 35 символов, 70 байтов

{⍵=1:0⋄k-⍨+/+/¨{w=⍵⊃v}¨⍳k←≢v←∪w←π⍵}

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

  f←{⍵=1:0⋄k-⍨+/+/¨{w=⍵⊃v}¨⍳k←≢v←∪w←π⍵}
  f¨1..15
0 0 0 1 0 0 0 2 1 0 0 1 0 0 0

RosLuP
источник

Чрезмерные целые числа

Вызов

Примеры

Ответы:

MATL , 7 5 байт

объяснение

Брахилог , 11 байт

объяснение

Mathematica, 23 байта

Желе , 5 байт

05AB1E , 6 байтов

J 11 10 байт

Pyth, 7 байт

C 74 байта

Python 2, 57 56 байт

Haskell, 65 байт

05AB1E , 4 байта

Python 2, 100 99 98 96 байт

Brachylog , 11 байт

СИЛОС , 113 байт

Javascript (ES6), 53 51 46 байт

Баш, 77 байт

Python, (с симпатией) 66 байт

CJam, 11 байт

GNU sed + coreutils, 55 байт

объяснение

APL (NARS) 35 символов, 70 байтов