Что такое кратчайший путь, по количеству символов, чтобы найти основные факторы в любом количестве?
Пример ввода: 1806046
Результат: 2x11x11x17x439
Что такое кратчайший путь, по количеству символов, чтобы найти основные факторы в любом количестве?
Пример ввода: 1806046
Результат: 2x11x11x17x439
С#, 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":""));};
}
}
}
Обязательный ответ J (2 символа):
q:
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));}
Математика (15 символов, включая скобки):
FactorInteger
Пример:
FactorInteger[42]
{{2, 1}, {3, 1}, {7, 1}}
Python: 77 символов со входом и выходом
d,s,n=2,'',input()
while n>1:
if n%d:d+=1
else:s+='%dx'%d;n/=d
print s[:-1]
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 (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
, а не четыре пробела. Он работает как еще один уровень отступов и стоит всего один символ вместо двух.
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)
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 позволяет обрабатывать числа произвольной длины.
11 символов в APL
Исключение заголовка функции и новых строк
factors←{2÷/∪⌽∧\⍵∨⍳⍵}
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 (через STDIN)
#!ruby -nrmathn
p$_.to_i.prime_division.map{|d,c|[d]*c}.flatten.join"x"
Ответ Mathematica, который фактически выдает указанный результат:
[email protected]@Riffle[[email protected]@[email protected]@@FactorInteger[n],x]
55 символов. Предполагается, что n
- это номер входа, а x
не имеет назначенного ему значения.
Лучший ответ Perl - 70 символов и никаких дополнительных модулей (если вы не учитываете специальные функции 5.10):
perl -nE'sub f{($a)[email protected]_;$a%$_||return$_,f($a/$_)for 2..$a}$,=x;say f$_'
Не работает 1 или 0, но отлично работает для всего остального. Если вам не нравится использовать say
или использует более раннюю версию Perl, здесь используется 81 символьная версия:
perl -ne'sub f{($a)[email protected]_;$a%$_||return$_,f($a/$_)for 2..$a;}$,=x;$/="\n";print f$_'
Perl, 223 символа
perl -ne'f($o=$_,2);sub f{($v,$f)[email protected]_;$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);}}}'
Ничего себе, вы, ребята, не очень хороши в оптимизации. Я могу сделать это в Perl в 63 символах или 79, если вы настаиваете на том, чтобы включить #!/Usr/bin/perl вверху:
use Math::Big::Factors;
@f=factor_wheel($ARGV[0],1);
print @f;
(Не смотрите на меня таким образом. Продвинутые программисты - ленивые программисты.)
Пока это не моя лучшая работа, здесь я отвечаю в 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
Я уверен, что больше можно сделать, но пока это хорошо.
Изменить: перестроить вещи, чтобы сбрить символ, менее эффективный, но меньший.
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
Perl, 70 char
$y=<>;for($i=2;$i<=$y;){next if$y%$i++;$y/=--$i;[email protected],$i}[email protected]{$,=x}
Эйфория: 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 символов
Мне не разрешено оставлять комментарии, но можно немного сократить предыдущий ответ, не имея Option 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
Язык программирования Go, 100 символов:
package main;func main(){n:=42;c:="x";for i:=2;n>1;i++{if n%i<1{n/=i;if(n<2){c=""};print(i,c);i--}}}
Моя программа с правильным отступом:
package main
func main() {
n := 42 // or whichever input number you like
c := "x" // separating printed integers
for i:=2 ; n>1; i++ {
if n%i<1 { // n%i==0
n /= i
if(n<2) { c = "" } // n==1
print(i, c)
i--
}
}
}
74 75 Персонажи в Python
a=input();b=2
while b*b<=a:
if a%b==0:print b;a/=b;b=1
b+=1
print a
Получено из моего кода TI-BASIC для простой факторизации.
Так как я говорю о TI-Basic...
77 Символы в TI-Basic
input a
2→b
while b²<a
a/b→c
if int(c)=c:then:disp b:c→a:1→b:end
b+1→b
end
disp a
С#, 366 символов
С# - не самый авербежный язык для чего-то подобного, но это довольно компактно:
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;
}
}
}
}
Edit:
Я видел, что Нолдорин использовал метод List.Find в своем коде F # и понял, что он будет немного короче, чем foreach...
Edit:
Ну, если это не обязательно полная программа...
С#, 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);}
С# и 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'));}
В том же духе, что и Paxinum (ответ Mathematica), здесь один из bash:
$ factor 1806046
1806046: 2 11 11 17 439
7 символов исключающее число.
Рекурсивное решение 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]
Обе версии подвержены переполнениям стека для всех, кроме самых маленьких.
В 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.
f="";
for(i=2;i<n;i++)
if(n%i==0){
f+=i+"x";
n/=i;i--
}
f+=n;
(54 символа)
сначала объявить n= the number to be factored
(включено 2 символа)
затем выполните код.
Пример:
> n=12345
12345
> f="";for(i=2;i<n;i++)if(n%i==0){f+=i+"x";n/=i;i--}f+=n
"3x5x823"
Без печати результата.
l,f,p=len,lambda n:list(filter(lambda b:n%b==0,range(2,n))),lambda n:l(f(n))==0;r=lambda n: n if p(n) else[x if p(x) else r(x) for x in [f(n)[0],f(n)[l(f(n))-1]]]
Используйте его как функцию:
print(r(1806046))