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 🐜

Odpowiedzi:

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: