Encontre os principais fatores

23

Nesta tarefa, você deve escrever um programa que calcule os fatores primos de um número. A entrada é um número natural 1 <n <2 ^ 32. A saída é uma lista dos fatores primos do número no seguinte formato. Os expoentes devem ser omitidos se forem 1. Somente imprima números primos. (Supondo que a entrada seja 131784):

131784 = 2 ^ 3 * 3 * 17 ^ 2 * 19

Não é necessário usar a mesma quantidade de espaço em branco; espaço em branco pode ser inserido sempre que apropriado. Seu programa deve ser concluído em menos de 10 minutos para qualquer entrada. O programa com a menor quantidade de caracteres vence.

FUZxxl
fonte
9
Pontos de bônus se seu programa puder levar 6857599914349403977654744967172758179904114264612947326127169976133296980951450542789808884504301075550786464802304019795402754670660318614966266413770127 em 73 dias!
Joey Adams
@Joey Adams: A fatoração começa com 17 * 71 * 113 * 997 * 313597 ...
FUZxxl
3
@FUZxxl: Acho que você cometeu um erro ao copiar o número. É o produto de dois primos grandes .
Joey Adams
@ Joey Podemos usar o algoritmo de Shor?
Mateen Ulhaq
23
@ Joey acidentalmente derramei café no meu computador quântico, e meu amigo está usando o dele para "invadir o governo dos EUA" ou algo sem importância, então não. :(
Mateen Ulhaq

Respostas:

11

SageMath, 31 bytes

N=input()
print N,"=",factor(N)

Caso de teste: 83891573479027823458394579234582347590825792034579235923475902312344444 Saídas:

83891573479027823458394579234582347590825792034579235923475902312344444 = 2^2 * 3^2 * 89395597 * 98966790508447596609239 * 263396636003096040031295425789508274613

12431234123412341234123
fonte
Parabéns por vencer um desafio com seu primeiro post, bom trabalho! E bem-vindo ao site!
DJMcMayhem
8

Ruby 1.9, 74 70 caracteres

#!ruby -plrmathn
$_+=?=+$_.to_i.prime_division.map{|a|a[0,a[1]]*?^}*?*

Edições:

  • (74 -> 70) Basta usar o expoente como comprimento da fatia em vez de procurar explicitamente exponent > 1
Ventero
fonte
7

Perl 5.10, 73 88

perl -pe '$_=`factor $_`;s%( \d+)\K\1+%-1-length($&)/length$1%ge;y, -,*^,;s;\D+;=;'

Toma o número da entrada da entrada padrão. Computará os fatores para várias entradas, se fornecidas.

Contado como uma diferença para perl -e. 5.10 é necessário para o \Kmetacaractere regex.

JB
fonte
+1 para usar factor.
st0le
Você não deveria contar a popção?
Joey #
@ Joey de fato eu deveria. Me desculpe por isso. Fixação.
JB
Ainda não testei isso, mas em vez de split/\D/,~factor $_~;$_="@_";escrever $_=~factor $_~;s/\D/ /g;? (Claro substituir ~com a crase.)
Timwi
Você quer dizer $_=`factor $_`;s/\D/ /g;? O revestimento duplo do backtick ajuda.
Aaaaaaaaaaaa
5

OCaml, 201 caracteres

Uma tradução imperativa direta do melhor código Python:

let(%)s d=if!d>1then Printf.printf"%s%d"s!d
let f n=let x,d,e,s=ref n,ref 1,ref 0,ref"="in""%x;while!d<65536do
incr d;e:=0;while!x mod!d=0do x:=!x/ !d;incr e
done;if!e>0then(!s%d;"^"%e;s:="*")done;!s%x

Por exemplo,

# f 4294967292;;
4294967292=2^2*3^2*7*11*31*151*331- : unit = ()

(observe que eu omiti a saída da linha final). Apenas por diversão, com 213 caracteres, uma versão puramente funcional, completamente ofuscada pelo uso liberal de operadores:

let(%)s d=if d>1then Printf.printf"%s%d"s d
let f x=let s=ref"="in""%x;let rec(@)x d=if d=65536then!s%x else
let rec(^)x e=if x/d*d<x then x,e else x/d^e+1in
let x,e=x^0in if e>0then(!s%d;"^"%e;s:="*");x@d+1in x@2
Matías Giovannini
fonte
5

Python, 140 135 133 caracteres

M=N=input()
s=''
f=1
while f<4**8:
 f+=1;e=0
 while N%f<1:e+=1;N/=f
 if e:s+='*%d'%f+'^%d'%e*(e>1)
print M,'=',(s+'*%d'%N*(N>1))[1:]
Keith Randall
fonte
Eu acho que a saída requer mais alguns espaços, por exemplo ' * %d'... E mais duas coisas 65536 == 4**8:; Linha 7:if e:s+='*%d'%f+'^%d'%e*(e>1)
Oleh Prypin
@ BlaXpirit: "mesma quantidade de espaço em branco não é necessária". Obrigado pelos outros dois, vou incorporá-los.
Keith Randall
5

J, 72

(":*/f),'=',([,'*',])/(":"0~.f),.(('^',":)`(''"0)@.(=&1))"0+/(=/~.)f=.q:161784

J. Típico Dois caracteres para fazer a maior parte do trabalho, sessenta caracteres para apresentá-lo.

Editar: corrigida a contagem de caracteres.

JB
fonte
2
Isso não me parece 62 caracteres. Mesmo quando assumindo 161784sua entrada, ainda tem 72 caracteres.
Ventero
Não seria mais curto com |: __ q: y?
Eelvex
2
@ Ventero: JB típico. Duas horas para jogar golfe, quinze segundos para atrapalhar a contagem de personagens.
JB
5

J, 53 52 caracteres

Essa solução segue o rplctruque da solução randomra, mas também traz algumas idéias originais.

":,'=',(":@{.,'^','*',~":@#)/.~@q:}:@rplc'^1*';'*'"_

Em notação não tácita, essa função se torna

f =: 3 : 0
(": y) , '=' , }: (g/.~ q: y) rplc '^1*' ; '*'
)

onde gé definido como

g =: 3 : 0
": {. y) , '^' , (": # y) , '*'
)
  • q: yé o vetor de fatores primos de y. Por exemplo, q: 60produz 2 2 3 5.
  • x u/. yaplica u- se a y keyed by x, isto é, ué aplicado a vetores de elementos ypara os quais as entradas xsão iguais. Isso é um pouco complexo para explicar, mas, no caso especial y u/. you u/.~ y, ué aplicado a cada vetor de elementos distintos em yque cada elemento é repetido tantas vezes quanto aparece y. Por exemplo, </.~ 1 2 1 2 3 1 2 2 3rendimentos

    ┌─────┬───────┬───┐
    │1 1 1│2 2 2 2│3 3│
    └─────┴───────┴───┘
    
  • # yé a contagem do ynúmero de itens em y.

  • ": y formata y como uma sequência.
  • x , y acrescenta x e y.
  • {. yé a cabeça y , ou seja, seu primeiro item.
  • Assim, (": {. y), '^' , (": # y) , '*'formata um vetor de n repetições de um número k em uma sequência da forma k ^ n *. Essa frase em notação tácita é a :@{.,'^','*',~":@#que passamos para o advérbio /.descrito mais adiante.
  • x rplc yé a função de biblioteca substituir caracteres. ytem a forma a ; be cada instância de corda aem xé substituída por b. xé embaralhado (ou seja, reformulado de forma a ter o rank 1) antes da operação, que é usada aqui. Este código substitui ^1*com *a cumprir com o formato de saída obrigatória.
  • }: yé a restrição de y, ou seja, todos, exceto seu último item. Isso é usado para remover o final *.
FUZxxl
fonte
Não foi possível economizar muito trabalho usando __ q:? Experimente online!
Adám 4/17/17
@ Adám De fato, boa ideia!
FUZxxl
4

PHP, 112

echo$n=$_GET[0],'=';$c=0;for($i=2;;){if($n%$i<1){$c++;$n/=$i;}else{if($c){echo"$i^$c*";}$c=0;if(++$i>$n)break;}}

118

echo $n=$_GET[0],'=';for($i=2;;){if(!($n%$i)){++$a[$i];$n/=$i;}else{if($a[$i])echo "$i^$a[$i]*";$i++;if($i>$n)break;}}
zzzzBov
fonte
3

Python 119 Chars

M=N=input()
i=1
s=""
while N>1:
 i+=1;c=0
 while N%i<1:c+=1;N/=i
 if c:s+=" * %d"%i+['','^%d'%c][c>1]
print M,'=',s[3:]
fR0DDY
fonte
1
Isso é o que eu tentei em primeiro lugar, mas é muito lento para grandes números primos, como 4294967291.
Keith Randall
@ Keith A questão permite até 10 minutos. Isso levará mais de 10 minutos para o pior caso?
FR0DDY 07/04
2
Demorou 32 minutos na minha máquina para esse número.
Keith Randall
3

JavaScript, 124 122 119

for(s='',i=2,o=p=prompt();i<o;i++){for(n=0;!(p%i);n++)p/=i;n?s+=i+(n-1?'^'+n:'')+'*':0}alert(s.substring(0,s.length-1))
Ry-
fonte
3

Perl, 78

use ntheory":all";say join" * ",map{(join"^",@$_)=~s/\^1$//r}factor_exp(shift)

Ele usa o recurso s /// r do Perl 5.14 para eliminar os ^ 1s. 81 caracteres para executar em um loop:

perl -Mntheory=:all -nE 'chomp;say join" * ",map{(join"^",@$_)=~s/\^1$//r}factor_exp($_);'
DanaJ
fonte
Você pode deixar de fora os espaços, se quiser. Isso salvaria dois caracteres. Ótima solução!
FUZxxl
2

PHP, 236 caracteres

$f[$n=$c=$argv[1]]++;echo"$n=";while($c){$c=0;foreach($f as$k=>$n)for($r=~~($k/2);$r>1;$r--){if($k%$r==0){unset($f[$k]);$f[$r]++;$f[$k/$r]++;$c=1;break;}}}foreach($f as$k=>$n)if(--$n)$f[$k]="$k^".++$n;else$f[$k]=$k;echo implode("*",$f);

Saída para 131784: 2 ^ 3 * 3 * 17 ^ 2 * 19

Conclui todos os números dentro de alguns segundos durante o teste.

4294967296=2^32
Time: 0.000168

A entrada nunca foi especificada, então eu escolhi chamá-la usando argumentos de linha de comando.

php factorize.php 4294967296
Kevin Brown
fonte
2

Scala 374:

def f(i:Int,c:Int=2):List[Int]=if(i==c)List(i)else 
if(i%c==0)c::f(i/c,c)else f(i,c+1)
val r=f(readInt)
class A(val v:Int,val c:Int,val l:List[(Int,Int)])
def g(a:A,i:Int)=if(a.v==i)new A(a.v,a.c+1,a.l)else new A(i,1,(a.v,a.c)::a.l)
val a=(new A(r.head,1,Nil:List[(Int,Int)])/:(r.tail:+0))((a,i)=>g(a,i))
a.l.map(p=>if(p._2==1)p._1 else p._1+"^"+p._2).mkString("", "*", "")

ungolfed:

def factorize (i: Int, c: Int = 2) : List [Int] = {
  if (i == c) List (i) else 
    if (i % c == 0) c :: f (i/c, c) else 
      f (i, c+1)
}
val r = factorize (readInt)
class A (val value: Int, val count: Int, val list: List [(Int, Int)])
def g (a: A, i: Int) = 
  if (a.value == i) 
    new A (a.value, a.count + 1, a.list) else 
    new A (i, 1, (a.value, a.count) :: a.list)
val a = (new A (r.head, 1, Nil: List[(Int,Int)]) /: (r.tail :+ 0)) ((a, i) => g (a, i))
a.l.map (p => if (p._2 == 1) p._1 else
  p._1 + "^" + p._2).mkString ("", "*", "")
Usuário desconhecido
fonte
2

J, 74 caracteres

f=.3 :0
(":y),'=',' '-.~('^1 ';'')rplc~}:,,&' *'"1(,'^'&,)&":/"{|:__ q:y
)

   f 131784
131784=2^3*3*17^2*19

64 caracteres com entrada na variável x:

   x=.131784

   (":x),'=',' '-.~('^1 ';'')rplc~}:,,&' *'"1(,'^'&,)&":/"{|:__ q:x
131784=2^3*3*17^2*19
randomra
fonte
Se você conseguir transformar isso em uma definição tácita, poderá evitar todas as aspas. Você também pode usar uma 3 : 0definição.
FUZxxl
@FUZxxl Eu esperava que eu pudesse colocar a string sem escape na 3 : 0versão, mas não funcionou de alguma forma. Eu posso tentar tácito mais tarde. Este é o 3: 0 que eu tentei: pastebin.com/rmTVAk4j .
Aleatório
Deveria funcionar. Eu não vejo o porquê. Você nomeou seu argumento ycomo deveria?
FUZxxl
@FUZxxl Este é o 3: 0 que eu tentei: pastebin.com/rmTVAk4j .
randomra
O 3: 0 que você tentou não corresponde exatamente ao one-liner que você fornece. Ele usa em ''vez de a:em um só lugar. Talvez essa seja a diferença?
FUZxxl
2

Java 10, 109 108 bytes (função lambda) (não concorrente a pedido do OP)

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

Experimente online.

Java 6+, 181 bytes (programa completo)

class M{public static void main(String[]a){long n=new Long(a[0]),i=1,f;String r=n+"=";for(;i++<n;r+=f<1?"":(f<2?i:i+"^"+f)+(n>1?"*":""))for(f=0;n%i<1;n/=i)f++;System.out.print(r);}}

Experimente online.

-1 byte graças a @ceilingcat .

Explicação:

n->{                // Method with integer parameter and String return-type
  var r=n+"=";      //  Result-String, starting at the input with an appended "="
  for(int i=1,f;i++<n;
                    //  Loop in the range [2, n]
      r+=           //    After every iteration: append the following to the result-String:
        f<1?        //     If the factor `f` is 0:
         ""         //      Append nothing
        :           //     Else:
         (f<2?      //      If the factor `f` is 1:
           i        //       Append the current prime `i`
          :         //      Else:
           i+"^"+f) //       Append the current prime `i` with it's factor `f`
         +(n>1?     //      And if we're not done yet:
            "*"     //       Also append a "*"
           :        //      Else:
            ""))    //       Append nothing more
    for(f=0;        //   Reset the factor `f` to 0
        n%i<1;      //   Loop as long as `n` is divisible by `i`
      n/=i)         //    Divide `n` by `i`
      f++;          //    Increase the factor `f` by 1
  return r;}        //  Return the result-String
Kevin Cruijssen
fonte
@ceilingcat Thanks!
Kevin Cruijssen
Desqualificado como o Java 10 foi criado após a publicação desta tarefa.
FUZxxl
@FUZxxl Marquei o Java 10 lambda como não concorrente e adicionei um programa Java 6, lançado em dezembro de 2006 .
Kevin Cruijssen
OK fixe. Isso funciona para mim!
FUZxxl
2

Japt , 28 27 26 bytes

-1 byte graças a Shaggy

+'=+Uk ü ®ÊÉ?ZÌ+'^+Zl:ZÃq*

Tente

Oliver
fonte
Desqualificado porque seu idioma foi criado após a publicação desta tarefa.
FUZxxl
1
@FUZxxl É permitido o uso de um idioma mais recente em um desafio antigo.
Oliver
Não foi permitido voltar quando o desafio foi lançado. Considero injusto alterar as regras de um desafio depois que o desafio foi publicado, para que os idiomas publicados após esse desafio permaneçam ilegais.
FUZxxl
1
@FUZxxl Você não precisa aceitar minha resposta, mas estou autorizado a responder de qualquer maneira.
Oliver
1
24 bytes
Shaggy
1

Powershell, 113 97 bytes

Inspirado pela resposta de Joey . É lento, mas curto.

param($x)(2..$x|%{for(;!($x%$_)){$_
$x/=$_}}|group|%{$_.Name+"^"+$_.Count-replace'\^1$'})-join'*'

Script de teste explicado:

$f = {

param($x)               # let $x stores a input number > 0
(2..$x|%{               # loop from 2 to initial input number
    for(;!($x%$_)){     # loop while remainder is 0
        $_              # push a current value to a pipe
        $x/=$_          # let $x is $x/$_ (new $x uses in for condition only)
    }
}|group|%{              # group all values
    $_.Name+"^"+$_.Count-replace'\^1$'  # format and remove last ^1
})-join'*'              # make string with *

}

&$f 2
&$f 126
&$f 129
&$f 86240
#&$f 7775460

Saída:

2
2*3^2*7
3*43
2^5*5*7^2*11
confuso
fonte
1

Gelatina , 16 bytes (não concorrente a pedido do OP)

³”=³ÆFḟ€1j€”^j”*

Uma das minhas primeiras respostas Jelly, então definitivamente posso jogar golfe (especialmente ³”=³) ..

Experimente online.

Explicação:

³                 # Push the first argument
 ”=               # Push string "="
   ³ÆF            # Get the prime factor-exponent pairs of the first argument
      ḟ€1         # Remove all 1s from each pair
         j€”^     # Join each pair by "^"
             j”*  # Join the pair of strings by "*"
                  # (implicitly join the entire 'stack' together)
                  # (which is output implicitly as result)
Kevin Cruijssen
fonte
Desqualificado porque seu idioma foi criado após a publicação desta tarefa.
FUZxxl
@FUZxxl Desde meados de 2017, a não concorrência não está mais na meta , a menos que o desafio afirme explicitamente que os idiomas devem ser mais antigos que o tempo da postagem. Mas se você, como quem postou o desafio, optar por não permitir idiomas mais recentes que o seu desafio após a data, editarei minhas respostas para adicionar o explícito (non-competing). :)
Kevin Cruijssen
Acredito que o consenso existente no local quando este desafio foi lançado deve definir as regras para respostas. Tudo o resto (isto é, regras que mudam após o lançamento do desafio) seria injusto. Marque suas respostas como não concorrentes.
FUZxxl
@FUZxxl Marquei minhas respostas como não concorrentes, conforme solicitado.
Kevin Cruijssen
Obrigado pela ajuda.
FUZxxl
1

05AB1E , 22 20 bytes (não concorrente a pedido do OP)

ÐfsÓ0Køε1K'^ý}'*ý'=ý

-2 bytes graças a @Emigna .

Experimente online.

Explicação:

Ð                # Triplicate the (implicit) input-integer
 f               # Pop and push all prime factors (without counting duplicates)
  s              # Swap to take the input again
   Ó             # Get all prime exponents
    0K           # Remove all 0s from the exponents list
      ø          # Zip it with the prime factors, creating pairs
       ε         # Map each pair to:
        1K       #  Remove all 1s from the pair
        '^ý     '#  And then join by "^"
       }'*ý     '# After the map: join the string/integers by "*"
           '=ý  '# And join the stack by "=" (with the input we triplicated at the start)
                 # (after which the result is output implicitly)
Kevin Cruijssen
fonte
1Kdeve funcionar em vez de `iy no loop.
Emigna
@ Emigna Ah lol .. Na verdade, eu faço isso na minha resposta Jelly que acabei de publicar . Não sei por que não pensei nisso antes aqui. :)
Kevin Cruijssen
Desqualificado porque seu idioma foi criado após a publicação desta tarefa.
FUZxxl
1

APL (NARS), 66 caracteres, 132 bytes

{(⍕⍵),'=',3↓∊{m←' * ',⍕↑⍵⋄1=w←2⊃⍵:m⋄m,'^',⍕w}¨v,¨+/¨{k=⍵}¨v←∪k←π⍵}

teste e comentário:

  f←{(⍕⍵),'=',3↓∊{m←' * ',⍕↑⍵⋄1=w←2⊃⍵:m⋄m,'^',⍕w}¨v,¨+/¨{k=⍵}¨v←∪k←π⍵}
  f 131784
131784=2^3 * 3 * 17^2 * 19
  f 2
2=2
  f (2*32)
4294967296=2^32

{(⍕⍵),'=',3↓∊{m←' * ',⍕↑⍵⋄1=w←2⊃⍵:m⋄m,'^',⍕w}¨v,¨+/¨{k=⍵}¨v←∪k←π⍵}
k←π⍵      find the factors with repetition of ⍵ and assign that array to k example for 12 k is 2 2 3
v←∪       gets from k unique elements and put them in array v
+/¨{k=⍵}¨ for each element of v count how many time it appear in k (it is array exponents)
v,¨       make array of couples from element of v (factors unique) and the array above (exponents unique)
∊{m←' * ',⍕↑⍵⋄1=w←2⊃⍵:m⋄m,'^',⍕w}¨ pretty print the array of couples factor exponent as array chars
3↓                                 but not the first 3 chars
(⍕⍵),'='  but print first the argument and '=' in char format

se alguém tem muito tempo com essas primitivas, conhece-as muito bem, para mim é possível que o código seja mais claro dos comentários ... portanto, código mais claro do que comentários, comentários inúteis ...

RosLuP
fonte
0

JavaScript, 107

n=prompt()
s=n+'='
c=0
for(i=2;;){if(n%i<1){c++
n/=i}else{if(c)s+=i+'^'+c+'*'
c=0
if(++i>n)break}}
alert(s)

120

n=prompt()
o={2:0}
for(i=2,c=n;i<=c;)!(c%i)?++o[i]?c/=i:0:o[++i]=0
s=n+'='
for(i in o)s+=o[i]?i+'^'+o[i]+'*':''
alert(s)
zzzzBov
fonte
1
Tem um à direita *na saída e imprime o expoente mesmo que seja 1.
Ventero
não há necessidade de voto negativo. Em nenhum lugar foi dito que não seria possível imprimir o expoente se fosse 1. Além disso, o final *pressupõe a multiplicação 1. Se for um problema tão grande, eu vou consertar.
ZzzzBov 09/04
1
»No formato a seguir« na descrição da tarefa implica praticamente que um expoente de 1não deve ser impresso. E não, um rastro *também é contra isso. Se alguém pudesse escolher livremente o formato de saída, então descascar factor(1)seria o mais fácil. As respostas podem ser razoavelmente comparadas se todas resolverem o mesmo problema.
9119 Joey
3
Como criador desta tarefa, digo, que os expoentes devem ser omitidos se 1 e apenas números primos puderem ser fatores.
FUZxxl
0

PHP , 112 bytes

<?=$a=$argn,"=";for($i=2;1<$a;)$a%$i?$i++:$a/=$i+!++$r[$i];foreach($r as$k=>$v)echo$t?"*":!++$t,$v<2?$k:"$k^$v";

Experimente online!

Jörg Hülsermann
fonte
0

PHP, 93 bytes

<?=$n=$argn;for($i=2;$n>1;$k&&$p=print($p?"*":"=")."$i^$k",$i++)for($k=0;$n%$i<1;$n/=$i)$k++;

Eu poderia fazer 89 bytes com o PHP 5.5 (ou posterior), mas isso atrasa o desafio em mais de 2 anos:

<?=$n=$argn;for($i=2;$n>1;$k&&$p=print"=*"[$p]."$i^$k",$i++)for($k=0;$n%$i<1;$n/=$i)$k++;

Execute como pipe -nFou experimente-os online .

Titus
fonte