Рассчитать основные факторы

27

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

Вызов

Напишите программу или функцию, которая принимает в качестве входных данных целое число больше 1 и выводит или возвращает список основных факторов.

правила

  • Ввод и вывод могут быть предоставлены любым стандартным методом и в любом стандартном формате.
  • Повторяющиеся факторы должны быть включены в вывод.
  • Вывод может быть в любом порядке.
  • Ввод будет не менее 2 или более 2 31 - 1.
  • Встроенные модули разрешены, но рекомендуется использовать не встроенное решение.

Контрольные примеры

2 -> 2
3 -> 3
4 -> 2, 2
6 -> 2, 3
8 -> 2, 2, 2
12 -> 2, 2, 3
255 -> 3, 5, 17
256 -> 2, 2, 2, 2, 2, 2, 2, 2
1001 -> 7, 11, 13
223092870 -> 2, 3, 5, 7, 11, 13, 17, 19, 23
2147483646 -> 2, 3, 3, 7, 11, 31, 151, 331
2147483647 -> 2147483647

счет

Это код-гольф , поэтому выигрывает самый короткий код в байтах.

code-golf primes factoring ETHproductions
источник
2
Было бы намного лучше, если бы вы запретили встроенные модули.
Чтение буфера
2
@TheBitByte Проблемы, которые запрещают встроенные программы, обычно рассматриваются как Do X без Y , особенно из-за того, что иногда трудно сказать, является ли решение технически встроенным.
ETHproductions
1
Ну что ж, наслаждайтесь притоком <5-байтовых решений! Когда я пишу это, Pyth уже делает это за 1 байт.
Чтение буфера
2
@TheBitByte Подумайте об этом, прежде всего, как о языке. Попробуйте обойти решение Python или другой язык без встроенного.
Исаак
1
@isaacg Ну, язык за языком - лучший способ взглянуть на это, я согласен.
Чтение буфера

Ответы:

15

Pyth , 1 байт

P

Мне нравятся шансы Пайта в этом испытании.

isaacg
источник
16
До тех пор, пока не появится язык "P" и не сделает это за 0 байтов
downrep_nation
13

Python 2 , 55 байт

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

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

Деннис
источник
1
Могу поспорить, у вас было это ожидание в течение большей части часа ...
ETHproductions
10

Python 2, 53 байта

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

Пытается каждый потенциальный делитель iпо очереди. Если iэто делитель, предваряет его и перезапускает n/i. Иначе, пробует следующий по величине делитель. Поскольку делители проверяются в порядке возрастания, найдены только простые.

Как программа, для 55 байтов:

n=input();i=2
while~-n:
 if n%i:i+=1
 else:n/=i;print i
XNOR
источник
8

Mathematica, 38 30 байт

Спасибо @MartinEnder за 8 байтов!

Join@@Table@@@FactorInteger@#&
Юнг Хван Мин
источник
Как насчет FactorInteger[#][[All, 1]]&? 26 байтов
Дэвид Дж. Аист
@ DavidG.Stork, который не сработает, потому что он не будет повторять главные факторы, если сила больше 1.
JungHwan Мин
4

JavaScript (ES6), 44 байта

f=(n,x=2)=>n-1?n%x?f(n,x+1):[x,...f(n/x)]:[]

Ужасно неэффективно из-за того, что он перебирает от 2 до каждого простого фактора, включая последний. Вы можете значительно сократить сложность времени за счет 5 байтов:

f=(n,x=2)=>x*x>n?[n]:n%x?f(n,x+1):[x,...f(n/x,x)]
ETHproductions
источник
3

На самом деле , 6 байтов

w`in`M

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

Объяснение:

w`in`M
w       factor into primes and exponents
 `in`M  repeat each prime # of times equal to exponent
Mego
источник
Вы можете, вероятно, просто использовать oсейчас, верно?
Оливер
@ Оливер Да, но я обычно не обновляю старые ответы встроенными.
Мего
3

J, 2 байта

q:

Тело должно быть не менее 30 символов.

alephalpha
источник
2

глухой , 3 байта

Этот язык довольно молодой и еще не совсем готов к чему-то важному, но он может выполнять простую факторизацию:

A/D

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

Када
источник
2

MATLAB, 6 байтов

Я думаю, что это не требует каких-либо объяснений.

factor
flawr
источник
1

Bash + coreutils, 19 байт

factor|sed s/.*:.//

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

Деннис
источник
Вы можете сбрить байт, если пробел не имеет значения при использовании factor|sed s/.*://. Также factor|cut -d: -f2(или factor|cut -d\ -f2для соответствия вашему текущему выводу) та же длина байта, но она будет работать быстрее и потреблять меньше памяти.
Калеб
Я спрошу у ОП про пробелы. К сожалению, мне нужноfactor|cut -d\ -f2- убрать начальное пространство, которое на один байт длиннее.
Деннис
1

Пакетный, 96 байт

@set/an=%1,f=2,r=0
:l
@set/af+=!!r,r=n%%f
@if %r%==0 echo %f%&set/an/=f
@if %n% gtr 1 goto l
Нил
источник
1

Hexagony , 58 байт

Пока не закончил игру в гольф, но @MartinEnder должен все равно это уничтожить

Распечатывает факторы, разделенные пробелом, с завершающим пробелом

Golfed:

2}\..}$?i6;>(<...=.\'/})."@...>%<..'':\}$"!>~\{=\)=\}&<.\\

Выложенная из:

     2 } \ . .
    } $ ? i 6 ;
   > ( < . . . =
  . \ ' / } ) . "
 @ . . . > % < . .
  ' ' : \ } $ " !
   > ~ \ { = \ )
    = \ } & < .
     \ \ . . .

Объяснение будет позже.

синий
источник
1

C 92 байта

int p(int n){for(int i=2;i<n;i++)if(n%i==0)return printf("%d, ",i)+p(n/i);printf("%d\n",n);}

Безголовая версия:

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>

int prime(int number) {
    for (int i = 2; i < number; i++) {
        if (number % i == 0) {
            printf("%d, ", i);
            return prime(number / i); //you can golf away a few bytes by returning the sum of your recursive function and the return of printf, which is an int
        }                             //this allow you to golf a few more bytes thanks to inline calls
    }
    printf("%d\n", number);
}

int main(int argc, char **argv) {
    prime(atoi(argv[1]));
}
Валентин Мариетт
источник
0

Perl 6 , 77 64 байта   

{my$a=$_;.is-prime??$_!!map ->\f{|({$a%f||($a/=f)&&f}...^*!= f)},(2... *>$a)}

Попытайся

{my$a=$_;map ->\f{|({$a%f||($a div=f)&&f}...^ f>*)},(2... *>$a)}

Попробуйте (Примечание: у него недостаточно времени, чтобы закончить)

Гораздо более производительная версия немного длиннее - 100 байт.

{my$a=$_;map ->\f{|({$a.is-prime??($/=$a)&&($a=0)||$/!!($a%f||($a div=f)&&f)}...^ f>*)},(2... *>$a)}

Попытайся

Расширен: (64-байтовая версия)

{
  my $a = $_;  # the input ｢$_｣ is read-only by default
  map
    -> \f {
      |(              # slip ( flattens into outer list )

        # generate sequence of 0 or more ｢f｣s
        {
          $a % f      # is it not evenly divisible

          ||          # if it is evenly divisible
          ($a div=f)  # divide it
          &&          # and
          f           # return ｢f｣
        }
        ...^   # keep doing that until
        f > *  # ｢f｣ is bigger
      )

    },

    # do that over the following list

    (2 ... * > $a) # generate a sequence from 2
                   # up to whatever the value of $a
                   # is at the time of the check
}
Брэд Гилберт b2gills
источник
0

VB.NET, 86 байт

Сидел ли это с некоторыми программами Project Euler. Убраны оптимизации в интересах краткости, и это результат. Естественно, VB очень многословен, поэтому он довольно длинный. Я не считаю ведущие пробелы. Его можно опустить, но с ним легче читать.

Это берет целое число в качестве параметра и печатает главные факторы с запятой после. В конце есть запятая.

Sub A(a)
    For i=2To a ' VB re-evaluates a each time, so the /= at the end of the loop shortens this
        While a Mod i=0 ' this is a factor. We've grabbed primes before this, so this must be a prime factor
            Console.Write(i &",") ' output
            a/=i ' "mark" the prime as "used"
        End While
    Next
End Sub
Брайан Дж
источник
0

Perl 6 , 51 байт

Рекурсивное решение:

sub f(\n,\d=2){n-1??n%d??f n,d+1!!(d,|f n/d,d)!!()}
Шон
источник
0

Java (OpenJDK) , 259 байт

import java.util.*;interface g{static void main(String[]z){int a=new Scanner(System.in).nextInt();int b=0;int[]l={};for(int i=2;i<=a;i++){for(;a%i<1;l[b-1]=i){l=Arrays.copyOf(l,b=l.length+1);a/=i;}}for(int i=0;i<b;i++)System.out.print(l[i]+(i<b-1?", ":""));}}

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

Павел
источник
Обратитесь к этой сути, чтобы увидеть, как это представление может быть использовано в дальнейшем: gist.github.com/kritixilithos/fde37dc5a8ae54852aa134a6e70ea495 . Если вам нужно что-то прояснить, не стесняйтесь пинговать меня на 19-м байте :)
Kritixi Lithos
0

Рубин, 61 байт

require'prime';->x{x.prime_division.flat_map{|x|[x[0]]*x[1]}}

Самая короткая встроенная версия, о которой я только мог подумать.

Seims
источник