Czasami, gdy bezczynnie próbuję uwzględnić liczbę, która pojawia się przede mną¹, po chwili zdaję sobie sprawę, że jest to łatwiejsze niż myślałem. Weźmy 2156na przykład: w końcu przychodzi mi do głowy, że jedno 21i drugie 56jest wielokrotnością 7, a więc na pewno 2156 = 21 x 100 + 56jest wielokrotnością 7.

Twoim zadaniem jest napisanie kodu, który identyfikuje liczby, które są łatwiejsze do obliczenia z powodu tego rodzaju zbiegu okoliczności.

Dokładniej:

Napisz program lub funkcję, która przyjmuje na nwejściu dodatnią liczbę całkowitą i zwraca prawdziwą wartość, jeśli istnieje dzielnik d(większy niż 1), który nmożna podzielić na dwie części, aby uzyskać dwie dodatnie liczby całkowite, z których każda jest wielokrotnością d; zwraca wartość fałsz, jeśli nie.

• „Posiekane na dwa” oznacza to, co myślisz: zwykła reprezentacja bazy-10 npodzielona w pewnym momencie na przednią i tylną połowę, aby uzyskać dwie inne liczby całkowite base-10. Jest w porządku, jeśli druga liczba całkowita ma wiodące zero (ale pamiętaj, że musi to być dodatnia liczba całkowita, więc podział 1230na 123i 0jest niepoprawny).
• Wartości prawdy i fałszu mogą zależeć od danych wejściowych. Na przykład, jeśli jakakolwiek niezerowa liczba całkowita jest zgodna z prawdą w wybranym języku, możesz zwrócić dzielnik dlub jeden z „elementów” n(lub nsam w tym zakresie).
• Na przykład dowolna liczba parzysta zawierająca co najmniej dwie cyfry w zestawie {2, 4, 6, 8}da prawdziwą wartość: po prostu podziel ją po pierwszej parzystej cyfrze. Na przykład każda liczba pierwsza nda wartość fałszowania, podobnie jak każda liczba jednocyfrowa.
• Zauważ, że wystarczy rozważyć podstawowe dzielniki d.
• Możesz założyć, że dane wejściowe są prawidłowe (dodatnia liczba całkowita).

To jest golf golfowy , więc wygrywa najkrótszy kod w bajtach. Ale rozwiązania we wszystkich językach są mile widziane, więc możemy dążyć do najkrótszego kodu w każdym języku, a nie tylko najkrótszego kodu w ogóle.

Przypadki testowe

(Musisz podać tylko wartość prawdy lub fałszu; poniższe adnotacje służą jedynie wyjaśnieniu). Niektóre dane wejściowe, które dają prawdziwe wartości, to:

39  (3 divides both 3 and 9)
64  (2 divides both 6 and 4)
497  (7 divides both 49 and 7)
990  (splitting into 99 and 0 is invalid; but 9 divides both 9 and 90)
2233  (11 divides both 22 and 33)
9156  (3 divides both 9 and 156; or, 7 divides both 91 and 56)
11791  (13 divides both 117 and 91)
91015  (5 divides both 910 and 15)
1912496621  (23 divides both 1912496 and 621; some splittings are multiples of 7 as well)
9372679892  (2473 divides both 937267 and 9892; some splittings are multiples of 2 as well)

Niektóre dane wejściowe, które dają wartości fałszowania, to:

52
61
130  (note that 13 and 0 is not a valid splitting)
691
899
2397
9029
26315
77300  (neither 7730 and 0 nor 773 and 00 are valid splittings)
2242593803

¹ tak, naprawdę to robię

Retina , 31 29 bajtów

,$';$`
\d+
$*
;(11+)\1*,\1+;

Wypróbuj online!

Zwraca dodatnią liczbę całkowitą dla prawidłowych danych wejściowych i zero dla danych nieprawidłowych.

Nie polecałbym czekania na większe przypadki testowe ...

Wyjaśnienie

,$';$`

W każdej pozycji wejścia wstaw przecinek, potem wszystko przed tą pozycją, potem średnik, a potem wszystko po tej pozycji. Co to robi Daje nam wszystkie możliwe podziały liczby (podzielone przez ,, oddzielone przez ;), a następnie dane wejściowe ponownie na końcu. Wejście 123staje się

,123;1,23;12,3;123,;123
     ^     ^     ^

gdzie zaznaczyłem oryginalne znaki wejściowe (to, co nie zostało oznaczone, to to, co wstawiliśmy). Zauważ, że powoduje to niepoprawne podziały, które nie są rzeczywistymi podziałami, i nie ma również znaczenia, czy wszystkie składowe końcowe są zerami, ale unikniemy ich później. Zaletą tworzenia niepoprawnych podziałów jest to, że wiemy, że każde prawidłowe podział ma znak ;z przodu i po nim, dzięki czemu możemy zapisać dwa bajty na granicach słów.

\d+
$*

Konwertuj każdą liczbę na jednoargumentową.

;(11+)\1*,\1+;

Dopasuj podział, dopasowując obie połówki jako wielokrotności pewnej liczby, która wynosi co najmniej 2.

Brachylog (2), 8 bajtów

~c₂ḋᵐ∋ᵐ=

Wypróbuj online!

Wyjaśnienie

~c₂ḋᵐ∋ᵐ=
~c₂       Split the input into two pieces
    ᵐ ᵐ   On each of those pieces:
   ḋ ∋      Choose a prime factor
       =  such that both the chosen factors are equal

Oczywiście, jeśli ta sama liczba (większa niż 1) dzieli obie części, ta sama liczba pierwsza podzieli obie. Wymaganie, aby czynnik był liczbą pierwszą, nie zezwala na 1 jako czynnik. Zapobiega to również 0wybraniu literału jako segmentu liczby (ponieważ 0nie ma on pierwszej faktoryzacji i spowoduje ḋawarię).

Nie ma potrzeby sprawdzania zgodności z wewnętrznymi zerami; jeśli podział na xi 0yjest poprawny x0i ybędzie działał równie dobrze (i idąc w drugą stronę, jeśli x0i ydziała, to mamy działające rozwiązanie niezależnie od tego, czy xi czy 0ybędzie działać, czy nie).

Pełny program Brachylog, taki jak ten, zwraca wartość logiczną; true.jeśli istnieje jakiś sposób, aby uruchomić go bez awarii (tj. dokonać takich wyborów, aby nie wystąpił błąd), false.jeśli wszystkie ścieżki prowadzą do awarii. Właśnie tego tu chcemy.

Galaretka , 14 12 11 10 bajtów

ŒṖḌo1g/€P>

Dzięki @JonathanAllan za grę w golfa na 1 bajcie!

Wypróbuj online!

Jak to działa

ŒṖḌo1g/€P>  Main link. Argument: n

ŒṖ          Compute all partitions of n's decimal digits.
  Ḍ         Undecimal; convert each array in each partition back to integer.
   o1       OR 1; replace disallowed zeroes with ones.
     g/€    Reduce (/) each (€) partition by GCD (g).
            The last GCD corresponds to the singleton partition and will always be
            equal to n. For a falsy input, all other GCDs will be 1.
        P   Take the product of all GCDs.
         >  Compare the product with n.

Mathematica, 63 62 bajty

(1 bajt dzięki Gregowi Martinowi)

1<Max@@GCD@@@Table[1~Max~#&/@Floor@{Mod[#,t=10^n],#/t},{n,#}]&

Jest to funkcja, która przyjmuje liczbę całkowitą jako dane wejściowe i zwraca Truelub False. Jeśli testujesz na dużej liczbie, przynieś książkę do przeczytania na czas oczekiwania.

Wyjaśnienie:

• Floor@{Mod[#,t=10^n],#/t}arytmetycznie dzieli dane wejściowe na ostatnie ncyfry i pozostałe m-ncyfry (gdzie mjest łączna liczba cyfr).
• Table[1~Max~#&/@...,{n,#}]robi to dla każdego ndo liczby wejściowej. (Jest to zdecydowanie za duże. Musimy to zrobić tylko do liczby cyfr na wejściu, ale w ten sposób oszczędzamy bajty i nadal dajemy prawidłowy wynik.) 1~Max~#&/@Bit pozbywa się zer, więc liczby takie jak 130 -> {13,0}się nie liczą jak True.
• 1<Max@@GCD@@@... znajduje największy wspólny dzielnik z każdej z tych par i sprawdza, czy którykolwiek z tych dzielników jest większy niż 1. Jeśli tak, to znaleźliśmy sposób na podzielenie liczby na czynniki.

Haskell , 57 bajtów

x#n|b<-mod x n=x>n&&(b>0&&gcd(div x n)b>1||x#(10*n))
(#1)

Wypróbuj online! Zastosowanie: (#1) 2156zwraca TruelubFalse

C, 145 142 139 139 135 135 bajtów

i,a,b;f(){char s[99];scanf("%s",s);for(char*p=s;*p++;)for(b=atoi(p),i=*p,*p=0,a=atoi(s),*p=i,i=1;i++<b;)*s=a%i-b%i|b%i?*s:0;return!*s;}

JavaScript (ES6), 74 71 70 bajtów

f=(s,t='',u)=>u?s%t?f(t,s%t,1):t:s&&f(t+=s[0],s=s.slice(1),1)>1|f(s,t)

<input oninput=o.textContent=f(this.value)><span id=o>

Pobiera dane wejściowe jako ciąg, co jest przydatne w przypadku fragmentu kodu. Edycja: Zapisano 3 bajty dzięki @ user81655.

Python 3, 133 118 117 bajtów

i,j=int,input()
from fractions import*
print(any(i(j[k:])*i(j[:k])*~-gcd(i(j[k:]),i(j[:k]))for k in range(1,len(j))))

Z pewnością nie najkrótszy, prawdopodobnie można go nieco skrócić. Działa na O(n)czas. Dane wejściowe są pobierane w formacie, \d+a dane wyjściowe są podawane w formacie zgodnym z (True|False)domyślną wartością logiczną Python
-3 bajtów dzięki Dead Possum
-15 bajtów dzięki ovs
-1 bajtów dzięki This Guy

QBIC , 91 90 bajtów

;_LA|[a-1|B=left$(A,b)┘C=right$(A,a-b)┘x=!B!┘y=!C![2,x|~(x>1)*(y>1)*(x%c=0)*(y%c=0)|_Xq}?0

Wyjaśnienie:

;               Get A$ from the command prompt
_LA|            Get the length of A$ and place it in a% (num var)
[a-1|           for b%=1; b% <= a%-1; b%++
B=left$(A,b)    break A$ in two components on index b%
C=right$(A,a-b)
x=!B!┘y=!C!     Convert both parts from string to num, assign to x% and y%
[2,x|           FOR c% = 2; c% <= x%; c%++

This next IF (~ in QBIC) is a bit ... iffy. It consists of a set of comparators.
Each comparator yields a -1 or a 0. We take the product of these. At any failed
comparison this will yield 0. When successful, it yields 1, which is seen as true by QBasic.

~(x>1)*(y>1)        IF X>1 and Y>1 --> this stops '00' and '1' splits.
*(x%c=0)*(y%c=0)    Trial divide the splits on loop counter c%.

|_Xq            Success? THEN END, and PRINT q (which is set to 1 in QBIC)
}               Close all language constructs (2 FOR loops and an IF)
?0              We didn't quit on match, so print 0

Python 3 , 70 69 bajtów

import math
f=lambda n,d=1:n>d and n%d*~-math.gcd(n//d,n%d)+f(n,10*d)

Wypróbuj online!

Perl 5 , 46 bajtów

43 bajty kodu + 3 bajty na -pflagę.

s~~$\|=grep!($`%$_|$'%$_),2..$`if$`*$'~ge}{

Wypróbuj online! lub wypróbuj zmodyfikowaną wersję umożliwiającą wiele danych wejściowych.
Prawdopodobnie nie chcesz wypróbować tego przy największym wejściu, ponieważ może to potrwać (bardzo długo).

Objaśnienia:
Iterujemy każdą pozycję w słowie z s~~~g, $`zawierając liczby przed i $'liczby po. Jeśli $`*$'jest to prawda (oznacza to, że żaden nie jest pusty, a żaden nie jest 0), wówczas sprawdzamy, czy liczba między 2 i $`dzieli oba z nich (za pomocą grep!(...),2..$`). Jeśli tak, $\|=..ustawi $\się na wartość niezerową, która jest domyślnie drukowana na końcu dzięki -pznacznikowi.

Python 2 , 69 bajtów

f=lambda n,d=10,k=2:k<d<n and(n/d%k+n%d%k<1<n%d)|f(n,d,k+1)|f(n,10*d)

Używa rekurencji zamiast wbudowanych GCD.

Wypróbuj online!

Jak to działa

Kiedy f jest wywoływany z jednego do trzech argumentów ( d domyślnie to 10 , k do 2 ), najpierw sprawdza wartość wyrażenia k<d<n. Jeśli obie nierówności k <d i d <n zostaną zachowane, wyrażenie po nim andzostanie wykonane i jego wartość zostanie zwrócona; w przeciwnym razie f po prostu zwróci False .

W pierwszym przypadku zaczynamy od oceny wyrażenia n/d%k+n%d%k<1<n%d.

d zawsze będzie potęgą dziesięciu, więc n/di n%dskutecznie podziel cyfry dziesiętne n na dwa wycinki. Te wycinki są podzielne przez k wtedy i tylko wtedy, gdy ma n/d%k+n%d%kwartość 0 , co jest testowane przez porównanie wyniku z 1 .

Ponieważ część wymagań jest taka, że ​​oba wycinki muszą reprezentować dodatnie liczby całkowite, wartość n%djest również porównywana z 1 . Zauważ, że 1 nie ma dzielników głównych, więc droższe porównanie z 0 nie jest wymagane. Zauważ też, że d <n już zapewnia, że n/dbędzie oceniać na dodatnią liczbę całkowitą.

Wreszcie rekurencyjnie wszystko f(n,d,k+1)(próba następnego potencjalnego wspólnego dzielnika) i f(n,10*d)(próba podziału) i zwraca logiczną OR wszystkich trzech wyników. Oznacza to, że f zwróci True, jeśli (i tylko jeśli) k jest wspólnym dzielnikiem n / d, a n% d lub tym samym jest prawdą dla większej wartości k i / lub wyższej potęgi dziesięciu d .