50

„Mrówka główna” jest upartym zwierzęciem, które porusza się po liczbach całkowitych i dzieli je, aż zostaną tylko liczby pierwsze!

Początkowo mamy nieskończoną tablicę A zawierającą wszystkie liczby całkowite> = 2: [2,3,4,5,6,.. ]

Niech pbędzie pozycją mrówki na tablicy. Początkowo p = 0(tablica jest indeksowana 0)

W każdej turze mrówka porusza się w następujący sposób:

jeśli A[p]jest liczbą pierwszą, mrówka przechodzi do następnej pozycji:p ← p+1
w przeciwnym razie, jeśli A[p]jest liczbą złożoną, niech qbędzie jej mniejszym dzielnikiem> 1. Dzielimy A[p]przez qi dodajemy qdo A[p-1]. Mrówka przesuwa się do poprzedniej pozycji:p ← p-1

Oto pierwsze ruchy mrówki:

 2  3  4  5  6  7  8  9  ... 
 ^
 2  3  4  5  6  7  8  9  ... 
    ^
 2  3  4  5  6  7  8  9  ... 
       ^
 2  5  2  5  6  7  8  9  ... 
    ^
 2  5  2  5  6  7  8  9  ... 
       ^
 2  5  2  5  6  7  8  9  ... 
          ^
 2  5  2  5  6  7  8  9  ... 
             ^
 2  5  2  7  3  7  8  9  ... 
          ^

Twój program powinien wyświetlać pozycję mrówki po nruchach. (możesz założyć n <= 10000)

Przypadki testowe:

0 => 0
10 => 6
47 => 9
4734 => 274
10000 => 512

Edytować. możesz również użyć 1-indeksowanych list, dopuszczalne jest wyświetlanie wyników 1, 7, 10, 275, 513 dla powyższego przypadku testowego.

To jest code-golf, więc wygrywa kod z najkrótszym kodem w bajtach.

code-golf sequence primes

— Arnaud
źródło

32

Szczerze mówiąc myślałem, że na moim ekranie jest mrówka, kiedy zobaczyłem to w Hot Network Questions.

— Kodos Johnson,

14

Zastanawiam się, czy sekwencja jest dobrze zdefiniowana dla arbitralnie dużych n(czy też przypadek złożony mógłby kiedykolwiek przesunąć mrówkę na lewo od inicjału 2).

— Martin Ender,

1

@ SuperChafouin, więc wyniki dla przypadków testowych mogą być następujące: 1,7,10,275,513jeśli podano indeksowanie 1? Czy nadal będą musieli dopasować twoje wyniki.

— Tom Carpenter,

12

@MartinEnder Kolejnym otwartym pytaniem jest to, czy liczba pierwsza> 7 może ostatecznie pozostać w tyle na zawsze.

— Arnauld,

2

@Arnauld Na tyle, na ile ruch n = 1 000 000 000 (gdzie p = 17156661), relacja między ip jest bardzo bliska p = n / (ln (n) * ln (ln (n))).

— Penguino

11

Alice , 45 bajtów

/o
\i@/.&wqh!]k.&[&w;;?c]dt.n$k&;[.?~:![?+!kq

Wypróbuj online!

Przeważnie prosta implementacja.

nCzasy zapętlania w Alicji zwykle wykonuje się przez naciśnięcie n-1czasów adresu zwrotnego , a następnie powrót na końcu każdej iteracji za pomocą k. Ostatnim razem przez pętlę kinstrukcja nie ma dokąd wrócić, a wykonywanie postępuje dalej.

Ten program używa tej samej kinstrukcji, aby zatrzymać wcześnie, gdy liczba jest liczbą pierwszą. W rezultacie końcowa iteracja zawsze przesunie mrówkę w lewo. Aby zrekompensować ten błąd, wykonujemy n+1iteracje na 1-indeksowej tablicy, co daje dokładnie pożądany rezultat (i daje skrzynkę n=0za darmo).

— Nitrodon
źródło

7

Python 2 , 120 bajtów

p=0
A=range(2,input()+2)
for _ in A:
 for q in range(2,A[p]):
	if A[p]%q<1:A[p]/=q;p-=1;A[p]+=q;break
 else:p+=1
print p

Wypróbuj online!

Ach, rzadki for- elsepętla! elseKlauzula jest wykonywana tylko wtedy, gdy fororganizm nie wyszła za break. W naszym przypadku oznacza to, że sprawdziliśmy wszystkie qs i nie znaleźliśmy żadnego z nich do podzielenia p.

— Lynn
źródło

7

Oktawa , 109 103 101 94 bajty

function i=a(n)i=1;for l=z=2:n+1
if nnz(q=factor(z(i)))>1
z(i--)/=p=q(1);z(i--)+=p;end
i++;end

Wypróbuj online!

Ten kod wyświetli pozycję w indeksowaniu 1, więc wyniki dla przypadków testowych to:

0 => 1
10 => 7
47 => 10
4734 => 275
10000 => 513

Ta wersja korzysta z niektórych optymalizacji Octave, więc nie jest kompatybilna z MATLAB. Poniższy kod jest wersją zgodną z MATLAB.

MATLAB, 130 123 118 117 bajtów

function i=a(n)
z=2:n+1;i=1;for l=z
q=factor(z(i));if nnz(q)>1
z(i)=z(i)/q(1);i=i-1;z(i)=z(i)+q(1);else
i=i+1;end
end

Używa indeksowania 1, jak w wersji Octave. Przetestowałem to dla wszystkich przypadków testowych w MATLAB. Jako przykład dane wyjściowe przy 100000 wynoszą 3675 (jednoindeksowanie).

Skomentowana wersja powyższego kodu:

function i=a(n)
    z=2:n+1;                %Create our field of numbers
    i=1;                    %Start of at index of 1 (MATLAB uses 1-indexing)
    for l=1:n               %For the required number of iterations
        q=factor(z(i));     %Calculate the prime factors of the current element
        if nnz(q)>1         %If there are more than one, then not prime
            z(i)=z(i)/q(1); %So divide current by the minimum
            i=i-1;          %Move back a step
            z(i)=z(i)+q(1); %And add on the minimum to the previous.
        else
            i=i+1;          %Otherwise we move to the next step
        end
    end

Co ciekawe, są to pozycje mrówek w funkcji liczby iteracji dla pierwszych 10000 wartości n.

Wydaje się prawdopodobne, że Mrówka prawdopodobnie dąży do nieskończoności, ale kto wie, wygląd może być mylący.

MATLAB: Zapisano 6 bajtów z forzamiast whilei usuwaniem nawiasów z if- Dzięki @Giuseppe
MATLAB: Zaoszczędź 2 bajty - dzięki @ Święta
Oktawa: Zaoszczędź 10 bajtów, używając Oktawy \=i +=operacji - Dzięki @Giuseppe
Oktawa: Zaoszczędź 2 bajty za pomocą i++i i--- Dzięki @LuisMendo
Oktawa: Zaoszczędź 7 bajtów - Dzięki @Schchises

— Tom Carpenter
źródło

Aby działało na TIO, myślę, że musisz enddopasować sygnaturę funkcji

— Giuseppe,

@Giuseppe Ah, ok. W MATLAB trailing endjest opcjonalny.

— Tom Carpenter,

możesz zrobić anonimową funkcję, używając @ (n) na początku zamiast funkcji i = a (n)

— Michthan

@Michthan nie może tego zrobić w MATLAB. Nie sądzę, że jest to możliwe w Octave, ponieważ ma pętle?

— Tom Carpenter,

1

Trailing endjest również opcjonalny w Octave. Jest to potrzebne tylko dlatego, że masz kod po funkcji

— Luis Mendo

6

JavaScript (ES6), 91 bajtów

f=(n,a=[p=0])=>n--?f(n,a,(P=n=>++x<n?n%x?P(n):a[a[p]/=x,--p]+=x:p++)(a[p]=a[p]||p+2,x=1)):p

Próbny

Uwaga: Może być konieczne zwiększenie domyślnego rozmiaru stosu silnika, aby przeszedł on wszystkie przypadki testowe.

Wypróbuj online!

— Arnauld
źródło

6

Haskell , 108 106 94 bajtów

([0]#[2..]!!)
(a:b)#(p:q)=length b:([b#(a+d:div p d:q)|d<-[2..p-1],mod p d<1]++[(p:a:b)#q])!!0

Wypróbuj online! Przykładowe użycie: ([0]#[2..]!!) 10plony 6(indeksowane 0).

Funkcja #działa na dwóch listach, odwróconym przodzie tablicy [p-1, p-2, ..., 1]i nieskończonej reszcie tablicy [p, p+1, p+2, ...]. Konstruuje nieskończoną listę pozycji, z której nzwracana jest pozycja th na podstawie danych wejściowych n.

Wzór ((a:b)#(p:q))wiąże psię z wartością bieżącej pozycji mrówki i awartością poprzedniej pozycji. bjest prefiks tablicy od pozycji 1 do p-2i qnieskończony reszty od pozycji p+1.

Budujemy listę wywołań rekurencyjnych w następujący sposób: Patrzymy na każdy dzielnik dz p(który jest większy niż jeden i mniejszy niż p) w kolejności rosnącej i dodać b#(a+d:div p d:q)do każdej z nich, to bieżąca wartość pdzieli się przez di mrówka porusza jeden krok w lewo, gdzie djest dodawany a. Następnie dołączamy (p:a:b)#qna końcu tej listy, co oznacza, że mrówka przesuwa się o krok w prawo.

Następnie pobieramy pierwsze z tych rekurencyjnych wywołań z listy i przygotowujemy bieżącą pozycję, która pokrywa się z długością listy prefiksów b. Ponieważ dzielniki są w porządku rosnącym, wybranie pierwszego z listy wywołań rekurencyjnych gwarantuje, że użyjemy najmniejszego. Ponadto, ponieważ (p:a:b)#qjest dodawany na końcu listy, jest wybierany tylko wtedy, gdy nie ma dzielników, a pzatem jest liczbą pierwszą.

Edycja:
-2 bajty, przełączając listę funkcji z malejącej na rosnącą.
-12 bajtów dzięki pomysłowi Zgarba na indeksowanie do nieskończonej listy zamiast obsługi licznika i przejście na indeksowanie 0.

— Laikoni
źródło

2

96 bajtów , budując nieskończoną listę i indeksując, zamiast nosić przy sobie licznik.

— Zgarb

1

@Zgarb Wielkie dzięki! Ma nawet 94 bajty przy przejściu na indeksowanie 0.

— Laikoni,

5

TI-BASIC, 108 103 102 98 bajtów

Wejścia i wyjścia są przechowywane w Ans. Dane wyjściowe są indeksowane 1.

Ans→N
seq(X,X,2,9³→A
1→P
For(I,1,N
1→X:∟A(P→V
For(F,2,√(V
If X and not(fPart(V/F:Then
DelVar XV/F→∟A(P
P-1→P
F+∟A(P→∟A(P
End
End
P+X→P
End

— kamoroso94
źródło

Możesz zdjąć bajt fPart(∟A(P)/F:z fPart(F¹∟A(P:. To samo w następnym wierszu.

— Scott Milner,

@ScottMilner To nie zawsze działa. not(fPart(7⁻¹7wynosi 0, ale not(fPart(7/7wynosi 1.

— kamoroso94 11.10.17

5

MATL , 41 bajtów

:Q1y"XHyw)Zp?5MQ}1MtYf1)/H(8MyfHq=*+9M]]&

Wyjście jest oparte na 1. Limit czasu programu dla ostatniego przypadku testowego w tłumaczu online.

Wypróbuj online!

Wyjaśnienie

Program stosuje procedurę opisaną w wyzwaniu. W tym celu niezwykle intensywnie wykorzystuje ręczne i automatyczne schowka MATL.

Najmniejszy dzielnik jest uzyskiwany jako pierwszy wpis w rozkładzie czynnika pierwszego.

„Podziału” zmiana odbywa się poprzez zastępowanie odpowiedniego wpisu tablicy A . „Dodaj” zmiana odbywa się poprzez element mądry dodanie do A w tablicy, który zawiera same zera, z wyjątkiem w pożądanym położeniu.

:Q        % Implicitly input n. Push array [2 3 ... n+1]. This is the initial array A. 
          % It contains all required positions. Some values will be overwritten
1         % Push 1. This is the initial value for p
y         % Duplicate from below
"         % For each loop. This executes the following n times.
          %   STACK (contents whosn bottom to top): A, p
  XH      %   Copy p into clipboard H
  y       %   Duplicate from below. STACK: A, p, A
  w       %   Swap. STACK: A, A, p
  )       %   Reference indexing. STACK: A, A[p]
  Zp      %   Isprime. STACK: A, false/true
  ?       %   If true (that is, if A[p] is prime)
    5M    %     Push p from automatic clipboard. STACK: A, p
    Q     %     Add 1. STACK: A, p+1
  }       %   Else (that is, if A[p] is not prime)
    1M    %     Push A[p] from automatic clipboard. STACK: A, A[p]
    t     %     Duplicate. STACK: A, A[p], A[p]
    Yf    %     Prime factors, with repetitions. STACK: A, A[p], prime factors of A[p]
    1)    %     Get first element, d. STACK: A, A[p], d
    /     %     Divide. STACK: A, A[p]/d
    H     %     Push p from clipboard H. STACK: A, A[p]/d, p
    (     %     Assignment indexing: write value. STACK: A with A[p] updated
    8M    %     Push d from automatic clipboard.
    y     %     Duplicate from below. STACK: A with A[p] updated, d, A with A[p] updated
    f     %     Find: push indices of nonzero entries.
          %     STACK: A with A[p] updated, d, [1 2 ... n]
    Hq    %     Push p from clipboard H, subtract 1.
          %     STACK: A with A[p] updated, d, [1 2 ... n], p-1
    =     %     Test for equality, element-wise.
          %     STACK: A with A[p] updated, d, [0 ... 0 1 0 ... 0]
    *     %     Multiply, element-wise. STACK: A with A[p] updated, [0 ... 0 d 0 ... 0]
    +     %     Add, element-wise. STACK: A with A[p-1] and A[p] updated
    9M    %     Push p-1 from automatic clipboard.
          %     STACK: A with A[p-1] and A[p] updated, p-1
  ]       %   End if. The stack contains the updated array and index
]         % End for each. Process the next iteration
&         % Specify that the following implicit display function should display only
          % the top of the stack. Implicitly display

— Luis Mendo
źródło

3

Pyth - 44 bajty

Proste wdrożenie proceduralne.

K}2hhQVQJ@KZIP_J=hZ).?=GhPJ XKZ/JG=tZ XZKG;Z

Pakiet testowy .

— Maltysen
źródło

3

PARI / GP, 87 bajtów

f(n)=A=[2..9^5];p=1;for(i=1,n,q=factor(A[p])[1,1];if(A[p]-q,A[p]/=q;p--;A[p]+=q,p++));p

Dość oczywiste (nie tak golfowo). Jeśli nie policzysz f(n)=części, to jest 82 bajtów. Możesz także zacząć od n->(85 bajtów).

Jest to język indeksowany 1.

Edycja: Modyfikacja illustrate(n,m)=A=[2..m+1];p=1;for(i=1,n,for(j=1,m,printf("%5s",if(j==p,Str(">",A[j],"<"),Str(A[j]," "))));print();q=factor(A[p])[1,1];if(A[p]!=q,A[p]/=q;p--;A[p]+=q,p++))wydrukuje ilustrację spaceru mrówki (biorąc pod uwagę wystarczająco szeroki terminal). Na przykład illustrate(150,25)da pierwsze 150 kroków na 25 kolumnach, takich jak to:

  > 2 <3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2> 3 <4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 3> 4 <5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2> 5 <2 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5> 2 <5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 2> 5 <6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 2 5> 6 <7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 2> 7 <3 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 2 7> 3 <7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 2 7 3> 7 <8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 2 7 3 7> 8 <9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 2 7 3> 9 <4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 2 7> 6 <3 4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 2> 9 <3 3 4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5> 5 <3 3 3 4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5> 3 <3 3 4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3> 3 <3 4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3> 3 <4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 3> 4 <9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3> 5 <2 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5> 2 <9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 2> 9 <10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5> 5 <3 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5> 3 <10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5 3> 10 <11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5> 5 <5 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5 5> 5 <11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5 5 5> 11 <12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5 5 5 11> 12 <13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5 5 5> 13 <6 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5 5 5 13> 6 <13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5 5 5> 15 <3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5 5> 8 <5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5> 7 <4 5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5 7> 4 <5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5 5> 9 <2 5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 5> 8 <3 2 5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3> 7 <4 3 2 5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3 7> 4 <3 2 5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3 3> 9 <2 3 2 5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 3> 6 <3 2 3 2 5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5> 5 <3 3 2 3 2 5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5> 3 <3 2 3 2 5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3> 3 <2 3 2 5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3> 2 <3 2 5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2> 3 <2 5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3> 2 <5 3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2> 5 <3 13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 5> 3 <13 14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 5 3> 13 <14 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 5 3 13> 14 <15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 5 3> 15 <7 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 5> 6 <5 7 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2> 7 <3 5 7 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7> 3 <5 7 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3> 5 <7 15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3 5> 7 <15 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3 5 7> 15 <16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3 5> 10 <5 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3> 7 <5 5 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3 7> 5 <5 16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3 7 5> 5 <16 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3 7 5 5> 16 <17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3 7 5> 7 <8 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3 7 5 7> 8 <17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3 7 5> 9 <4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3 7> 8 <3 4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7 3> 9 <4 3 4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2 7> 6 <3 4 3 4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 2> 9 <3 3 4 3 4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3> 5 <3 3 3 4 3 4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5> 3 <3 3 4 3 4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3> 3 <3 4 3 4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3> 3 <4 3 4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 3> 4 <3 4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3> 5 <2 3 4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5> 2 <3 4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2> 3 <4 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 3> 4 <17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2> 5 <2 17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 5> 2 <17 18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 5 2> 17 <18 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 5 2 17> 18 <19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 5 2> 19 <9 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 5 2 19> 9 <19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 5 2> 22 <3 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 5> 4 <11 3 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2> 7 <2 11 3 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7> 2 <11 3 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2> 11 <3 19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2 11> 3 <19 20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2 11 3> 19 <20 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2 11 3 19> 20 <21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2 11 3> 21 <10 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2 11> 6 <7 10 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2> 13 <3 7 10 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2 13> 3 <7 10 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2 13 3> 7 <10 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2 13 3 7> 10 <21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2 13 3> 9 <5 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2 13> 6 <3 5 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 2> 15 <3 3 5 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7> 5 <5 3 3 5 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5> 5 <3 3 5 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5> 3 <3 5 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3> 3 <5 21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 3> 5 <21 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 3 5> 21 <22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 3> 8 <7 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3> 5 <4 7 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 5> 4 <7 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3> 7 <2 7 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7> 2 <7 22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 2> 7 <22 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 2 7> 22 <23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 2> 9 <11 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7> 5 <3 11 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 5> 3 <11 23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 5 3> 11 <23 24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 5 3 11> 23 <24 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 5 3 11 23> 24 <25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 5 3 11> 25 <12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 5 3> 16 <5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 5> 5 <8 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 5 5> 8 <5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 5> 7 <4 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 5 7> 4 <5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7 5> 9 <2 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3 7> 8 <3 2 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5 3> 9 <4 3 2 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 5> 6 <3 4 3 2 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5> 7 <3 3 4 3 2 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7> 3 <3 4 3 2 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3> 3 <4 3 2 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 3> 4 <3 2 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3> 5 <2 3 2 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5> 2 <3 2 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2> 3 <2 5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2 3> 2 <5 12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2 3 2> 5 <12 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2 3 2 5> 12 <25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2 3 2> 7 <6 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2 3 2 7> 6 <25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2 3 2> 9 <3 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2 3> 5 <3 3 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2 3 5> 3 <3 25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2 3 5 3> 3 <25 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2 3 5 3 3> 25 <26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2 3 5 3> 8 <5 26
   2 5 5 5 3 3 2 3 5 3 3 5 2 7 5 7 3 5 2 3 5> 5 <4 5 26

— Jeppe Stig Nielsen
źródło

2

Python 2 , 142 127 bajtów

Zaoszczędź piętnaście bajtów dzięki Sherlockowi9 .

T=range(2,input()+2);p=0
for _ in T:
 m=T[p];d=min(k for k in range(2,m+1)if m%k<1);p+=1
 if d<m:T[p-1]/=d;p-=2;T[p]+=d
print p

Wypróbuj online!

— Jonathan Frech
źródło

127 bajtów, jeśli nie używaszP(n)

— Sherlock9

126 bajtów

— Felipe Nardi Batista

@FelipeNardiBatista Niestety twoja sugestia wydaje się nie działać w przypadkach testowychn<=4

— Sherlock9

2

Mathematica, 118 103 bajty

(s=Range[2,5^6];t=1;Do[If[PrimeQ@s[[t]],t++,s[[t]]/=(k=#2&@@ Divisors@s[[t]]);s[[t-1]]+=k;t--],#];t-1)&

Wypróbuj online!

Martin Ender zapisał 15 bajtów

— J42161217
źródło

Miałeś przed sobą zbłąkane miejsce Divisors, możesz użyć notacji infix dla Doi możesz po prostu wrócić tzamiast t-1(wynik na podstawie 1).

— Martin Ender,

2

Python 3 , 158 149 133 bajtów

Jest to prosta implementacja proceduralna z jednym lub dwoma dziwactwami, aby upewnić się, że kod działa dla wszystkich przypadków testowych. Używam, [*range(2,n+9)]aby upewnić się, że A jest wystarczająco duże (z wyjątkiem n<3, że n+9jest więcej niż wystarczające). elseKlauzula dzieli stary A[p]przez d, ubytków p, a następnie dodaje dsię nowy A[p], który jest zdecydowanie złe praktyki kodowania. W przeciwnym razie całkiem proste. Zapraszamy do gry w golfa!

Edycja: -9 bajtów bez sympypodziękowań dla Halvarda Hummela. -14 bajtów od Felipe Nardi Batista, -6 bajtów z niektórych wskazówek z odpowiedzi Jonathana Frecha na Python 2

p,_,*A=range(int(input())+2)
for _ in A:
 m=A[p];d=min(k for k in range(2,m+1)if m%k<1);p+=1
 if d<m:A[p-1]//=d;p-=2;A[p]+=d
print(p)

Wypróbuj online!

— Sherlock9
źródło

145 bajtów

— Halvard Hummel

148 bajtów, dzięki czemu jest to pełny program

— Felipe Nardi Batista

if d-m:A[p]...i else:p+=1by uratować bajt

— Felipe Nardi Batista

143 bajty poprzez usunięcie elseoświadczenia

— Felipe Nardi Batista

po usunięciu elseinstrukcji nie ma różnicy w bajtach w stosunku do wersji funkcji

— Felipe Nardi Batista

2

PHP, 102 + 1 bajtów

for($a=range(2,$argn);$argn--;$d<$a[+$p]?$a[$p--]/=$d+!$a[$p]+=$d:$p++)for($d=1;$a[+$p]%++$d;);echo$p;

Uruchom jako potok z -Rlub spróbuj online .

Puste wyjście dla danych wejściowych 0; wstaw +po echoliterał0

lub użyj tej 1-indeksowanej wersji (103 + 1 bajtów):

for($a=range($p=1,$argn);$argn--;$d<$a[$p]?$a[$p--]/=$d+!$a[$p]+=$d:$p++)for($d=1;$a[$p]%++$d;);echo$p;

— Tytus
źródło

2

R , 123 bajty

Prosta implementacja. Jest on dostarczany jako funkcja, która przyjmuje liczbę ruchów jako dane wejściowe i zwraca pozycję p.

Zapętla sekwencję i przesuwa wskaźnik do przodu i do tyłu zgodnie z zasadami. Dane wyjściowe są oparte na 0.

Uwaga: aby znaleźć najmniejszy czynnik pierwszy liczby x, oblicza moduł x względem wszystkich liczb całkowitych od 0 do x. Następnie wyodrębnia liczby o module równym 0, które zawsze wynoszą [0,1, ..., x]. Jeśli trzecią taką liczbą nie jest x, to jest to najmniejszy czynnik pierwszy x.

p=function(l){w=0:l;v=w+1;j=1;for(i in w){y=v[j];x=w[!y%%w][3]
if(x%in%c(NA,y))j=j+1
else{v[j]=y/x;j=j-1;v[j]=v[j]+x}}
j-2}

Wypróbuj online!

— Nie dotyczy
źródło

2

C (gcc), 152 148 bajtów

Zminimalizowane

int f(int n){int*A=malloc(++n*4),p=0,i,q;for(i=0;i<n;i++)A[i]=i+2;for(i=1;i<n;i++){for(q=2;A[p]%q;q++);if(A[p++]>q){A[--p]/=q;A[--p]+=q;}}return p;}

Sformułowany z kilkoma komentarzami

int f(int n) {
  int *A = malloc(++n * 4), p = 0, i, q;
  // Initialize array A
  for (i = 0; i < n; i++)
    A[i] = i + 2;
  // Do n step (remember n was incremented)
  for (i = 1; i < n; i++) {
    // Find smallest divisor
    for (q = 2; A[p] % q; q++)
      ;
    if (A[p++] > q) {
      A[--p] /= q;
      A[--p] += q;
    }
  }
  return p;
}

Główna funkcja do testowania

#include <stdlib.h>
#include <stdio.h>
int main(int argc, char **argv) {
  if (argc != 2)
    return 2;
  int n = atoi(argv[1]);
  int p = f(n);
  printf("%d => %d\n", n, p);
  return 0;
}

Za pokazanie każdego kroku

Deklaracja wyświetlania () wewnątrz f ()

int f(int n) {
  int *A = malloc(++n * 4), p = 0, i, q;
  void display(void) {
    for (int i=0; i < p; i++) {
      printf(" %d", A[i]);
    }
    printf(" \033[1;31m%d\033[m", A[p]);
    if (p+1 < n)
      printf(" %d", A[p+1]);
    printf("\n");
  }
  ...

Wyświetlanie połączeń ()
```
  A[i] = i + 2;
display();
```
Wyświetlanie połączeń ()
```
  }
  display();
}
```

— użytkownik285259
źródło

Możesz zgolić niektóre bajty , deklarując A jako tablicę i inicjalizując kontrolki pętli przed pętlami, jeśli to możliwe, prawda?

— Przywróć Monikę

1

Clojure, 185 bajtów

#(loop[[n p][(vec(range 2 1e3))0]i %](if(= i 0)p(recur(if-let[q(first(for[i(range 2(n p)):when(=(mod(n p)i)0)]i))][(assoc n p(/(n p)q)(dec p)(+(n(dec p))q))(dec p)][n(inc p)])(dec i))))

Otóż edytowanie „stanu” nie jest idealne w Clojure. Musisz zwiększyć wykładnik w przypadku większych nakładów.

— NikoNyrh
źródło

Dlaczego użyłeś dopasowania wzorca w loop? Bez tego powinieneś być w stanie stracić kilka bajtów.

— clismique

Ponadto możesz być w stanie zmienić firstrzecz na someinstrukcję.

— clismique

Bez dopasowania wzorca musiałem powtórzyć recurdwa razy, po jednym dla każdej if-letgałęzi. Zostanie również (dec i)skopiowany. somepotrzebuje predykatu, mógłbym użyć, +ponieważ mamy do czynienia z liczbami, ale jest to jeden znak dłuższy niż first. CMIIW

— NikoNyrh

1

Java 8, 138 135 bajtów

n->{int a[]=new int[++n],s=0,p=0,j=0;for(;j<n;a[j++]=j+1);for(;++s<n;p++)for(j=1;++j<a[p];)if(a[p]%j<1){a[p--]/=j;a[p--]+=j;}return p;}

Wyjaśnienie:

Wypróbuj tutaj.

n->{                     // Method with integer as both parameter and return-type
  int a[]=new int[++n],  //  Integer-array with a length of `n+1`
      s=0,               //  Steps-counter (starting at 0)
      p=0,               //  Current position (starting at 0)
      j=0;               //  Index integer (starting at 0)
  for(;j<n;              //  Loop (1) from 0 to the input (inclusive due to `++n` above)
    a[j++]=j+1           //   And fill the array with 2 through `n+2`
  );                     //  End of loop (1)
  for(;++s<n;            //  Loop (2) `n` amount of steps:
      p++)               //    And after every iteration: increase position `p` by 1
    for(j=1;             //   Reset `j` to 1
        ++j<a[p];)       //   Inner loop (3) from 2 to `a[p]` (the current item)
      if(a[p]%j<1){      //    If the current item is divisible by `j`:
        a[p--]/=j;       //     Divide the current item by `j`
        a[p--]+=j;}      //     And increase the previous item by `j`
                         //     And set position `p` two steps back (with both `p--`)
                         //   End of inner loop (3) (implicit / single-line body)
                         //  End of loop (2) (implicit / single-line body)
  return p;              //  Return the resulting position `p`
}                        // End of method

— Kevin Cruijssen
źródło

1

Clojure, 198 193 191 bajtów

To wymaga poważnego golfa ...

#(loop[i(vec(range 2(+ % 9)))c 0 p 0](if(= % c)p(let[d(dec p)u(i p)f(some(fn[n](if(=(mod u n)0)n))(range 2(inc u)))e(= u f)](recur(if e i(assoc i d(+(i d)f)p(/ u f)))(inc c)(if e(inc p)d)))))

Golf 1 : Zapisano 5 bajtów, zmieniając (first(filter ...))na(some ...)

Golf 2 : Zapisano 2 bajty, zmieniając (zero? ...)na(= ... 0)

Stosowanie:

(#(...) 10000) => 512

Nieskluczony kod:

(defn prime-ant [n]
  (loop [counter 0
         pos 0
         items (vec (range 2 (+ n 9)))]
    (if (= n counter) pos
      (let [cur-item (nth items pos)
            prime-factor
            (some #(if (zero? (mod cur-item %)) %)
              (range 2 (inc cur-item)))
            equals? (= cur-item prime-factor)]
        (recur
          (inc counter)
          (if equals? (inc pos) (dec pos))
          (if equals? items
            (assoc items
              (dec pos) (+ (items (dec pos)) prime-factor)
              pos (/ cur-item prime-factor))))))))

— clismique
źródło

Pierwotna mrówka 🐜

Alice , 45 bajtów

Python 2 , 120 bajtów

Oktawa , 109 103 101 94 bajty

MATLAB, 130 123 118 117 bajtów

JavaScript (ES6), 91 bajtów

Próbny

Haskell , 108 106 94 bajtów

TI-BASIC, 108 103 102 98 bajtów

MATL , 41 bajtów

Wyjaśnienie

Pyth - 44 bajty

PARI / GP, 87 bajtów

Python 2 , 142 127 bajtów

Mathematica, 118 103 bajty

Python 3 , 158 149 133 bajtów

PHP, 102 + 1 bajtów

R , 123 bajty

C (gcc), 152 148 bajtów

Zminimalizowane

Sformułowany z kilkoma komentarzami

Główna funkcja do testowania

Za pokazanie każdego kroku

Clojure, 185 bajtów

Java 8, 138 135 bajtów

Clojure, 198 193 191 bajtów

Stosowanie:

Nieskluczony kod: