Найдите главные факторы

23

В этой задаче вы должны написать программу, которая вычисляет основные множители числа. Ввод представляет собой натуральное число 1 <n <2 ^ 32. Выходные данные представляют собой список основных факторов числа в следующем формате. Экспоненты должны быть опущены, если они равны 1. Выведите только простые числа. (Предполагая, что ввод 131784):

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

Использование одинакового количества пробелов не требуется; пробелы могут быть вставлены, где это уместно. Ваша программа должна завершиться менее чем за 10 минут для любого ввода. Программа с кратчайшим количеством символов выигрывает.

FUZxxl
источник
9
Бонусные баллы, если ваша программа может учитывать 68575999143494039776547449671727581799041142646129473261271699761332969809514505427898088845043010755507864648023040197954027546706603186149662664138614966266413770127 меньше, чем 7373!
Джои Адамс
@ Джои Адамс: Факторизация начинается с 17 * 71 * 113 * 997 * 313597 ...
FUZxxl
3
@FUZxxl: Я думаю, что вы сделали ошибку, копируя номер. Это произведение двух больших простых чисел .
Джои Адамс,
@Joey Можем ли мы использовать алгоритм Шора?
Матин Улхак
23
@ Джои Я случайно пролил немного кофе на свой квантовый компьютер, и мой друг использует его, чтобы «взломать правительство США» или что-то неважное, так что нет. :(
Матеин Улхак

Ответы:

11

SageMath, 31 байт

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

Тестовый пример: 83891573479027823458394579234582347590825792034579235923475902312344444 Выходы:

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

+12431234123412341234123
источник
Поздравляю с победой в первом посте, отличная работа! И добро пожаловать на сайт!
DJMcMayhem
8

Рубин 1.9, 74 70 персонажей

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

Редактирование:

  • (74 -> 70) Просто используйте показатель степени в качестве длины среза вместо явной проверки exponent > 1
Ventero
источник
7

Perl 5.10, 73 88

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

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

Считается как разница perl -e. 5.10 необходим для \Kметасимвола регулярных выражений.

JB
источник
+1 за использование factor.
st0le
Разве вы не можете рассчитывать pвариант?
Джои
@ Джои, действительно, я должен. Прости за это. Закрепление.
JB
Не проверял это, но вместо того, split/\D/,~factor $_~;$_="@_";чтобы написать $_=~factor $_~;s/\D/ /g;? (Конечно, заменить ~на обратный
удар
Вы имеете в виду $_=`factor $_`;s/\D/ /g;? Двойная защитная оболочка помогает.
aaaaaaaaaaaa
5

OCaml, 201 символ

Прямой императивный перевод лучшего кода 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

Например,

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

(обратите внимание, что я пропустил вывод окончательной конечной строки.) Ради интереса, 213 символов, чисто функциональная версия, полностью запутанная благодаря свободному использованию операторов:

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
Матиас Джованнини
источник
5

Питон, 140 135 133 символов

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:]
Кит Рэндалл
источник
Я думаю, что вывод требует еще несколько пробелов, например ' * %d'... И еще две вещи 65536 == 4**8:; Строка 7:if e:s+='*%d'%f+'^%d'%e*(e>1)
Олег Припин
@BlaXpirit: «одинаковое количество пробелов не требуется». Спасибо за другие два, я включу их.
Кит Рэндалл
5

J, 72

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

Типичный J. Два персонажа для выполнения большей части работы, шестьдесят символов для представления.

Редактировать: Исправлено количество символов.

JB
источник
2
Это не похоже на 62 символа для меня. Даже если предположить, 161784что вы вводите, это по-прежнему 72 символа.
Вентеро
Не будет ли это короче |: __ q: y?
Eelvex
2
@Ventero: типичный JB. Два часа на игру в гольф, и пятнадцать секунд, чтобы испортить счет персонажа.
JB
5

J, 53 52 символа

Это решение берет rplcуловку от решения randomra, но также предлагает некоторые оригинальные идеи.

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

В неявной нотации эта функция становится

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

где gопределяется как

g =: 3 : 0
": {. y) , '^' , (": # y) , '*'
)
  • q: yявляется вектором главных факторов в y. Например, q: 60урожайность 2 2 3 5.
  • x u/. yотносится uк y шпонке с x, то есть, uприменяются для векторов элементов , yдля которых запись в xравна. Это немного сложно объяснить, но в частном случае , y u/. yили u/.~ y, uприменяется к каждому вектору различных элементов y, где каждый элемент повторяется для так часто , как он появляется в y. Например, </.~ 1 2 1 2 3 1 2 2 3урожайность

    ┌─────┬───────┬───┐
    │1 1 1│2 2 2 2│3 3│
    └─────┴───────┴───┘
    
  • # yэто число из y, то есть, количество элементов y.

  • ": y форматирует y как строку.
  • x , y добавляет x иy .
  • {. yэто голова y , то есть ее первый элемент.
  • Таким образом, (": {. y), '^' , (": # y) , '*'форматирует вектор из n повторений числа k в строку вида k ^ n *. Эта фраза в молчаливом обозначении есть :@{.,'^','*',~":@#, которую мы передаем наречие, /.описанному выше выше.
  • x rplc yявляется библиотечной функцией замены символов yимеет форму, a ; bи каждый экземпляр строки aв xзаменяется на b. xперед операцией происходит выравнивание (то есть изменение формы таким образом, чтобы оно имело ранг 1), что используется здесь. Этот код заменяется ^1*на *как соответствующий обязательному формату вывода.
  • }: yявляется Лишать из y, то есть все , но его последний элемент. Это используется для удаления трейлинга *.
FUZxxl
источник
Не могли бы вы сэкономить много работы с помощью __ q:? Попробуйте онлайн!
Адам
@ Adám Действительно, хорошая идея!
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
источник
3

Питон 119 символов

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
источник
1
Это то, что я попробовал в первую очередь, но это слишком медленно для больших простых чисел, таких как 4294967291.
Кит Рэндалл
@Keith Вопрос позволяет до 10 минут. В худшем случае это займет более 10 минут?
fR0DDY
2
Это заняло 32 минуты на моей машине для этого числа.
Кит Рэндалл
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))
Рыбаковым
источник
3

Perl, 78

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

Он использует функцию s /// r в Perl 5.14 для исключения ^ 1s. 81 символов для запуска в цикле:

perl -Mntheory=:all -nE 'chomp;say join" * ",map{(join"^",@$_)=~s/\^1$//r}factor_exp($_);'
DanaJ
источник
Вы можете оставить пробелы, если хотите. Это спасло бы двух персонажей. Отличное решение!
FUZxxl
2

PHP, 236 символов

$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);

Выход для 131784: 2 ^ 3 * 3 * 17 ^ 2 * 19

Завершает все числа в течение нескольких секунд во время тестирования.

4294967296=2^32
Time: 0.000168

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

php factorize.php 4294967296
Кевин Браун
источник
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 ("", "*", "")
неизвестный пользователь
источник
2

J, 74 знака

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

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

64 символа с вводом в переменную x:

   x=.131784

   (":x),'=',' '-.~('^1 ';'')rplc~}:,,&' *'"1(,'^'&,)&":/"{|:__ q:x
131784=2^3*3*17^2*19
randomra
источник
Если вам удастся превратить это в неявное определение, вы можете избежать экранирования всех кавычек. Вы также можете использовать определение 3 : 0.
FUZxxl
@FUZxxl Я ожидал, что могу просто вставить неэкранированную строку в 3 : 0версии, но она почему-то не сработала. Я мог бы попытаться молчаливый позже, хотя. Это 3: 0 я попробовал: pastebin.com/rmTVAk4j .
рандома
Он должен работать. Я не понимаю почему. Вы назвали свой аргумент, yкак вы должны?
FUZxxl
@FUZxxl Это 3: 0, который я попробовал: pastebin.com/rmTVAk4j .
Рандомра
Попытка 3: 0 не совсем соответствует предоставленной вами строчке. Используется ''вместо того, чтобы a:в одном месте. Может в этом разница?
FUZxxl
2

Java 10, 109 108 байт (лямбда-функция) (не конкурирует по запросу 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;}

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

Java 6+, 181 байт (полная программа)

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);}}

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

-1 байт благодаря @ceilingcat .

Объяснение:

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
Кевин Круйссен
источник
@ceilingcat Спасибо!
Кевин Круйссен
Дисквалифицировано, поскольку Java 10 была создана после публикации этой задачи.
FUZxxl
@FUZxxl Я отметил лямбду Java 10 как не конкурирующую и добавил программу на Java 6, выпущенную в декабре 2006 года .
Кевин Круйссен
ОК, круто. Это подходит для меня!
FUZxxl
2

Джапт , 28 27 26 байт

-1 байт благодаря Shaggy

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

Попытайся

Оливер
источник
Дисквалифицирован, поскольку ваш язык был создан после публикации этого задания.
FUZxxl
Не было разрешено вернуться, когда вызов был опубликован. Я считаю несправедливым вносить изменения в правила конкурса после его опубликования, поэтому языки, опубликованные после этого конкурса, остаются незаконными.
FUZxxl
1
@FUZxxl Вы не должны принимать мой ответ, но я могу ответить на него независимо.
Оливер
1
24 байта
лохматый
1

Powershell, 113 97 байт

Вдохновленный ответом Джои . Это медленно, но коротко.

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

Пояснил тестовый скрипт:

$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

Выход:

2
2*3^2*7
3*43
2^5*5*7^2*11
Mazzy
источник
1

Желе , 16 байт (не конкурирует по запросу OP)

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

Один из моих первых ответов Jelly, так что определенно можно сыграть в гольф (особенно ³”=³ ) ..

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

Объяснение:

³                 # 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)
Кевин Круйссен
источник
Дисквалифицирован, поскольку ваш язык был создан после публикации этого задания.
FUZxxl
@FUZxxl С середины 2017 года неконкурентоспособность больше не находится в мета-версии , если только в задаче явно не указано, что языки должны быть старше, чем время публикации. Но если вы, как тот, кто опубликовал запрос, решите не разрешать использование языков, более новых, чем ваша дата пост-даты, я отредактирую свои ответы, чтобы добавить явное (non-competing). :)
Кевин Круйссен
Я полагаю, что консенсус сайта, который был на момент публикации этого задания, должен определять правила ответов. Все остальное (то есть правила, которые меняются после публикации заявки) будет несправедливым. Пожалуйста, отметьте ваши ответы как не конкурирующие.
FUZxxl
@FUZxxl Я пометил свои ответы как не конкурирующие, как и просил.
Кевин Круйссен
Спасибо за помощь.
FUZxxl
1

05AB1E , 22 20 байт (не конкурирует по запросу OP)

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

-2 байта благодаря @Emigna .

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

Объяснение:

Ð                # 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)
Кевин Круйссен
источник
1Kдолжен работать вместо `≠ iy в цикле.
Эминья
@ Emigna А, лол .. Я действительно делаю это в своем ответе на желе, который я только что опубликовал . Не уверен, почему я не думал об этом раньше здесь. :)
Кевин Круйссен
Дисквалифицирован, поскольку ваш язык был создан после публикации этого задания.
FUZxxl
1

APL (NARS), 66 символов, 132 байта

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

тест и комментарий:

  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

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

RosLuP
источник
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
источник
1
Имеет трейлинг *на выходе и печатает экспоненту, даже если она
равна
не надо понижать голос. Нигде не сказано, что он не может вывести показатель степени, если он равен 1. Кроме того, трейлинг *предполагает умножение на 1. Если это большая проблема, я ее исправлю.
zzzzBov
1
»В следующем формате« в описании задачи в значительной степени подразумевает, что показатель степени 1не должен быть напечатан. И нет, трейлинг *тоже против этого. Если бы можно было свободно выбрать выходной формат, тогда factor(1)проще всего было бы использовать оболочку. Ответы могут быть разумно сопоставлены, только если все они решают одну и ту же проблему.
Джои
3
Как создатель этой задачи, я говорю, что показатели должны быть опущены, если 1 и только простые числа могут быть факторами.
FUZxxl
0

PHP, 93 байта

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

Я мог бы сделать 89 байтов с PHP 5.5 (или позже), но это откладывает задачу на более чем 2 года:

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

Запустите как трубу с -nFили попробуйте их онлайн .

Titus
источник