Гольф кода: простые множители числа [закрываются]
При передаче значением:
void func(Object o);
и затем вызов
func(a);
Вы создадите Object на стеке, и в рамках реализации func на него сошлются o. Это могло бы все еще быть мелкой копией (внутренности a, и o мог бы указать на те же данные), таким образом a мог бы быть изменен. Однако, если o будет глубокая копия a, то a не изменится.
При передаче ссылкой:
void func2(Object& o);
и затем вызов
func2(a);
Вы будете только уступать новому дорогу для ссылки a". a" и" o" два названия того же объекта. Изменение o внутренний func2 будет делать те изменения видимыми в вызывающую сторону, которая знает объект именем" a".
25 ответов
C #, 69
x - входной номер
int i=2;while(x>1)if(x%i++==0){x/=--i;Console.Write(i+(x>1?"x":""));};
С включает:
using system;
namespace nameSP
{
class Program
{
static void Main(string[] args)
{
int i=2;while(x>1)if(x%i++==0){x/=--i;Console.Write(i+(x>1?"x":""));};
}
}
}
В том же ключе, что и Paxinum (ответ Mathematica), вот один в bash:
$ factor 1806046
1806046: 2 11 11 17 439
7 символов исключающее число.
В PARLANSE это поможет (252 символа):
(action (procedure natural)
(loop
(ifthen (== ? 1) (return))
(do f i 2 ? 1
(ifthen (== (modulo ? i) 0)
(print ?)
(= ? (/ ? i))
(exit f)
)ifthen
)do
)loop
)action
Я уверен, что для этого есть гораздо меньшая программа APL.
VB6 / VBA - 190 символов
Public Function P(N As Long) As String
Dim I As Long, O As String
Do While N > 1: For I = 2 To N
If N Mod I = 0 Then
O = O & " " & I: N = N / I: Exit For: End If: Next: Loop: P = O: End Function
C # и LINQ, 241 символ :
public IEnumerable<int> F(int n)
{
return Enumerable.Range(2,n-1)
.Where(x => (n%x)==0 && F(x).Count()==1)
.Take(1)
.SelectMany(x => new[]{x}.Concat(F(n/x)))
.DefaultIfEmpty(n);
}
public string Factor(int n) {
return F(n).Aggregate("", (s,i) => s+"x"+i).TrimStart('x');
}
Сжатый:
int[] F(int n){return Enumerable.Range(2,n-1).Where(x=>(n%x)==0&&F(x).Length==1).Take(1).SelectMany(x=>new[]{x}.Concat(F(n/x))).DefaultIfEmpty(n).ToArray();}void G(int n){Console.WriteLine(F(n).Aggregate("",(s,i)=>s+"x"+i).TrimStart('x'));}
Хотя это не лучшая моя работа, вот мой ответ на Haskell, 83 символа.
f n = s [2..n] n
s [] _ = []
s (p:z) n = p:s [x | x<-z, mod x p /= 0, mod n x == 0] n
Я уверен, что можно было бы сделать больше, но пока это хорошо.
Править : Переставил вещи, чтобы сбрить персонажа, менее эффективно, но меньше.
Лучший ответ Perl на данный момент - 70 символов и никаких дополнительных модулей (если вы не учитываете специальные функции 5.10):
perl -nE'sub f{($a)=@_;$a%$_||return$_,f($a/$_)for 2..$a}$,=x;say f$_'
Не работает для 1 или 0, но отлично работает для всего остального . Если вам не нравится использовать , скажем , или вы используете более раннюю версию Perl, вот версия из 81 символа:
perl -ne'sub f{($a)=@_;$a%$_||return$_,f($a/$_)for 2..$a;}$,=x;$/="\n";print f$_'
Haskell, 53 символа: (включая 3 символа новой строки)
a%1=[]
a%n|mod n a<1=a:p(div n a)|1>0=(a+1)%n
p=(2%)
Пример:
*Main> p 1806046
[2,11,11,17,439]
Python: 77 символов с вводом и выводом
d,s,n=2,'',input()
while n>1:
if n%d:d+=1
else:s+='%dx'%d;n/=d
print s[:-1]
ANSI C, 79 символов
main(d,i){for(d+=scanf("%d",&i);i>1;i%d?++d:printf("%d%c",d,(i/=d)>1?'x':10));}
Mathematica (15 символов, включая скобки):
FactorInteger
Пример:
FactorInteger[42]
{{2, 1}, {3, 1}, {7, 1}}
Ух ты, ребята, не очень хорошо разбираешься в оптимизации. Я могу сделать это на Perl в 63 символа,
C #, 366 символов
C # не самый сложный язык для чего-то вроде этого, но он довольно компактен:
class P {
static void Main(string[] a) {
int i = int.Parse(a[0]);
var p = new System.Collections.Generic.List<int>();
for (int n = 2; i > 1; n++)
if (p.Find(q => n % q == 0) == 0) {
p.Add(n);
while (i % n == 0) {
System.Console.WriteLine(n);
i /= n;
}
}
}
}
Изменить:
Я увидел, что Нолдорин использовал метод List.Find в своем коде F #, и понял, что он будет немного короче, чем foreach ...
Изменить:
Что ж, если это не должна быть полная программа ...
C #, 181 символ
string f(int i) {
var r = "";
var p = new System.Collections.Generic.List<int>();
for (int n = 2; i > 1; n++)
if (p.Find(q => n % q == 0) == 0) {
p.Add(n);
while (i % n == 0) {
r += "x" + n;
i /= n;
}
}
return r.Substring(1);
}
Сжатый:
string f(int i){var r="";var p=new System.Collections.Generic.List<int>();for(int n=2;i>1;n++)if(p.Find(q=>n%q==0)==0){p.Add(n);while(i%n==0){r+="x"+n;i/=n;}}return r.Substring(1);}
Perl, 223 символа
perl -ne'f($o=$_,2);sub f{($v,$f)=@_;$d=$v/$f;if(!($d-int($d))){print"$f ";if(!p($d)){print"$d ";return(0);}else{f($d,$f);}}else{while(p(++$f)){}f($v,$f);}}sub p{for($i=2;$i<=sqrt($_[0]);$i++){if($_[0]%$i==0){return(1);}}}'
F #
81 символ
let rec f n=if n=1 then[]else let a=[2..n]|>List.find(fun x->n%x=0)in a::f(n/a)
Это ужасно неэффективно, но поскольку цель, несомненно, состоит в том, чтобы написать максимально короткий код, я пренебрегал этим вопросом.
Читаемая форма (с использованием #light синтаксис):
let rec factorise n =
if n = 1 then [] else
let a = [2 .. n] |> List.find (fun x -> n % x = 0)
a :: factorise (n / a)
Erlang, ядро - 122 символа и 152 для всего модуля:
-module(pf).
-export([f/1]).
f(N) -> f(N,2,[]).
f(1,_,L) -> lists:reverse(L);
f(N,P,L) when N rem P == 0 -> f(N div P,P,[P|L]);
f(N,P,L) -> f(N,P+1,L).
Для вызова с консоли:
70> string:join([integer_to_list(X) || X <- pf:f(1806046)], "x").
"2x11x11x17x439"
Ruby 39B 71B (via STDIN)
#!ruby -nrmathn
p$_.to_i.prime_division.map{|d,c|[d]*c}.flatten.join"x"
Python (228 символов без ввода-вывода, 340 с):
import sys
def primeFactors(n):
l = []
while n > 1:
for i in xrange(2,n+1):
if n % i == 0:
l.append(i)
n = n // i
break
return l if len(l) > 0 else [n]
n = int(sys.argv[1])
print '%d: %s' % (n, 'x'.join(map(lambda x: str(x), primeFactors(n))))
Может быть сжат до 120 символов:
import sys
n,l=int(sys.argv[1]),[]
while n>1:
for i in range(2,n+1):
if n%i==0:l+=[str(i)];n/=i;break
print'x'.join(l)
Примечание. Это символ табуляции перед if , а не четыре пробела. Он работает как еще один уровень отступа и стоит только один символ вместо двух.
GNU bc , 47 символов, включая сбор входных данных (необходимы расширения GNU для print , else и read ]):
x=read();for(i=2;x>1;)if(x%i){i+=1}else{x/=i;i}
Если вам действительно нужны символы x на выходе, это 64 символа:
x=read();for(i=2;x>1;)if(x%i){i+=1}else{x/=i;print i;if(x>1)"x"}
Также обратите внимание, что использование bc позволяет обрабатывать числа произвольной длины.
Perl, 70 символов
$y=<>;for($i=2;$i<=$y;){next if$y%$i++;$y/=--$i;push@x,$i}print@{$,=x}
Ответ системы Mathematica, который фактически дает указанный результат:
Print@@Riffle[Join@@ConstantArray@@@FactorInteger[n],x]
55 символов. Предполагается, что n - это входной номер, а x не имеет присвоенного ему значения.
Euphoria: 106 символов
procedure f(atom a)atom x=2
loop do
while remainder(a,x)do
x+=1
end while
?x
a/=x
until a=1
end procedure
VB6/VBA - 147 chars
Я не могу оставлять комментарии, но могу несколько сократить предыдущий ответ, не имея Опции Explicit. Воспользовавшись некоторыми из наиболее опасных возможностей VB6/VBA, можно воспользоваться нижеприведенной опцией. Нет необходимости объявлять, что является переменной, а также функция не должна быть объявлена публично, если вы хотите получить максимальную короткую запись! Также End If не нужен, если она находится на той же строке.
Function P(N As Long)
Dim I, O
Do While N > 1: For I = 2 To N
If N Mod I = 0 Then O = O & " " & I: N = N / I: Exit For:
Next: Loop: P = O
End Function
Это можно проверить с помощью :
Public Sub TestP()
Dim s: s = P(1806046)
Debug.Print s
End Sub
Рекурсивное решение на Python
99 символов (включая пробелы) 87 символов (без пробелов)
def f(n,i=2,r=""):
while n%i<1:r+="%dx"%i;n/=i
return f(n,i+1,r)if n>1 else r
print f(input())[:-1]
Обновление: Полностью рекурсивная версия
def f(n,i=2,x=""): return x if n<2 else f(n,i+1,x)if n%i else f(n/i,i,x+'%dx'%i)
print f(input())[:-1]
Обе версии склонны к переполнению стека для всех входов, кроме самых маленьких.