Parfois, lorsque j'essaie paresseusement de prendre en compte le nombre qui apparaît devant moi¹, après un certain temps, je me rends compte que c'est plus facile que je ne le pensais. Prenons 2156par exemple: il m'est finalement apparu que les deux 21et 56sont des multiples de 7, et donc certainement 2156 = 21 x 100 + 56aussi un multiple de 7.

Votre tâche consiste à écrire du code qui identifie les nombres plus faciles à factoriser en raison d'une coïncidence de ce type.

Plus précisément:

Écrivez un programme ou une fonction qui prend nen entrée un entier positif et renvoie une valeur vraie s'il existe un diviseur d(supérieur à 1) tel qu'il npeut être coupé en deux pour produire deux entiers positifs, chacun étant un multiple de d; retourner une valeur falsifiée sinon.

• "Coupé en deux" signifie ce que vous pensez: la représentation habituelle en base 10 de npartitionnée à un moment donné en une moitié avant et une moitié arrière pour donner deux autres entiers de base 10. Ce n'est pas grave si le deuxième entier a un zéro non significatif (mais notez que ce doit être un entier positif, donc le fractionnement 1230en 123et 0n'est pas valide).
• Les valeurs véridiques et fausses peuvent dépendre de l'entrée. Par exemple, si un entier différent de zéro est véridique dans la langue de votre choix, vous pouvez renvoyer le diviseur dou l'un des "morceaux" de n(ou nlui - même d'ailleurs).
• Par exemple, tout nombre pair avec au moins deux chiffres dans l'ensemble {2, 4, 6, 8}donnera une valeur vraie: il suffit de le diviser après le premier chiffre pair. De même, par exemple, tout nombre premier ndonnera une valeur fausse, tout comme n'importe quel nombre à un chiffre.
• Notez qu'il suffit de considérer les diviseurs premiers d.
• Vous pouvez supposer que l'entrée est valide (c'est-à-dire un entier positif).

Il s'agit de code-golf , donc le code le plus court en octets l'emporte. Mais les solutions dans toutes les langues sont les bienvenues, nous pouvons donc nous efforcer d'obtenir le code le plus court dans chaque langue, et pas seulement le code le plus court dans l'ensemble.

Cas de test

(Vous n'avez qu'à sortir une valeur véridique ou fausse; les annotations ci-dessous sont juste à titre d'explication.) Certaines entrées qui donnent des valeurs véridiques sont:

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)

Certaines entrées qui donnent des valeurs de falsification sont:

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

¹ oui je fais vraiment ça

Rétine , 31 29 octets

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

Essayez-le en ligne!

Génère un entier positif pour les entrées valides et zéro pour les entrées non valides.

Je ne recommanderais pas d'attendre les plus grands cas de test ...

Explication

,$';$`

À chaque position de l'entrée, insérez une virgule, puis tout ce qui précède cette position, puis un point-virgule, puis tout ce qui se trouve après cette position. Qu'est-ce que ça fait? Il nous donne toutes les séparations possibles d'un nombre (divisé par ,, séparé par ;), puis à nouveau l'entrée à la fin. Donc, l'entrée 123devient

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

où j'ai marqué les caractères d'entrée originaux (le truc qui n'est pas marqué est ce que nous avons inséré). Notez que cela crée des séparations non valides qui ne sont pas des séparations réelles et que le composant de fin n'est pas entièrement composé de zéros, mais nous éviterons de les accepter plus tard. L'avantage de créer des séparations non valides est que nous savons que chaque fractionnement valide a un ;avant et un après, afin que nous puissions économiser deux octets sur les limites des mots.

\d+
$*

Convertissez chaque nombre en unaire.

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

Faites correspondre un fractionnement en faisant correspondre les deux moitiés sous forme de multiples d'un nombre d'au moins 2.

Brachylog (2), 8 octets

~c₂ḋᵐ∋ᵐ=

Essayez-le en ligne!

Explication

~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

De toute évidence, si le même nombre (supérieur à 1) divise les deux pièces, le même nombre premier divisera les deux. Exiger que le facteur soit premier interdit clairement 1 comme facteur. Il empêche également un littéral d' 0être choisi comme segment d'un nombre (car il 0n'a pas de factorisation principale et entraînera l' ḋéchec).

Il n'est pas nécessaire de vérifier les zéros internes correspondants; si une scission xet 0yest valide, x0et yfonctionnera tout aussi bien (et aller dans l'autre sens, si x0et ytravaux, nous avons une solution de travail indépendamment du fait que xet 0ytravaillerions ou non).

Un programme complet Brachylog, comme celui-ci, renvoie un booléen; true.s'il existe un moyen de l'exécuter sans échec (c'est-à-dire de faire des choix tels qu'aucune erreur ne se produise), false.si tous les chemins mènent à l'échec. C'est exactement ce que nous voulons ici.

Gelée , 14 12 11 10 octets

ŒṖḌo1g/€P>

Merci à @JonathanAllan d'avoir joué au golf sur 1 octet!

Essayez-le en ligne!

Comment ça marche

ŒṖḌ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 octets

(1 octet merci à Greg Martin)

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

C'est une fonction qui prend un entier en entrée et retourne Trueou False. Si vous le testez sur un grand nombre, apportez un livre à lire pendant que vous attendez.

Explication:

• Floor@{Mod[#,t=10^n],#/t}divise arithmétiquement l'entrée en ses derniers nchiffres et les m-nchiffres restants (où mest le nombre total de chiffres).
• Table[1~Max~#&/@...,{n,#}]fait cela pour chaque njusqu'au numéro d'entrée. (C'est beaucoup trop grand. Nous n'avons besoin que de faire cela jusqu'au nombre de chiffres de l'entrée, mais cette façon économise les octets et donne toujours le résultat correct.) Le 1~Max~#&/@bit se débarrasse des zéros, donc les nombres comme 130 -> {13,0}ne comptent pas comme True.
• 1<Max@@GCD@@@... trouve le plus grand diviseur commun de chacune de ces paires et vérifie si l'un de ces diviseurs est supérieur à 1. Si tel est le cas, nous avons trouvé un moyen de factoriser le nombre en le divisant.

Haskell , 57 octets

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

Essayez-le en ligne! Utilisation:, (#1) 2156retourne TrueouFalse

C, 145 142 139 138 138 135 octets

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 octets

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>

Prend l'entrée sous forme de chaîne, ce qui est pratique pour l'extrait de code. Edit: sauvé 3 octets grâce à @ user81655.

Python 3, 133 118 117 117 octets

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))))

Certainement pas le plus court, pourrait probablement être un peu raccourci. Fonctionne dans le O(n)temps. L'entrée est prise au format \d+et la sortie est donnée au format (True|False)selon la valeur booléenne Python par défaut
-3 octets grâce à Dead Possum
-15 octets grâce à ovs
-1 octet grâce à This Guy

QBIC , 91 90 octets

;_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

Explication:

;               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 octets

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

Essayez-le en ligne!

Perl 5 , 46 octets

43 octets de code + 3 octets pour l' -pindicateur.

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

Essayez-le en ligne! ou essayez cette version modifiée permettant plusieurs entrées.
Vous ne voudrez probablement pas essayer ceci sur la plus grande entrée, car cela pourrait prendre un (très long) temps.

Explications:
Nous parcourons chaque position du mot avec s~~~g, en $`contenant les nombres avant et $'les nombres après. Si $`*$'est vrai (cela signifie qu'aucun n'est vide et aucun n'est 0), alors nous vérifions si un nombre entre 2 et les $`divisons tous les deux (avec le grep!(...),2..$`). Si oui, $\|=..définira$\ sur une valeur non nulle, qui est implicitement imprimée à la fin grâce à -pflag.

Python 2 , 69 octets

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)

Utilise la récursivité au lieu des fonctions intégrées GCD.

Essayez-le en ligne!

Comment ça marche

Lorsque f est appelé avec un à trois arguments ( d par défaut est 10 , k à 2 ), il vérifie d'abord la valeur de l'expression k<d<n. Si les inégalités k <d et d <n sont toutes deux valides, l'expression suivante andest exécutée et sa valeur est renvoyée; sinon, f retournera simplement False .

Dans le premier cas, nous commençons par évaluer l'expression n/d%k+n%d%k<1<n%d.

d sera toujours une puissance de dix, doncn/d et n%ddivisez efficacement les chiffres décimaux de n en deux tranches. Ces tranches sont à la fois divisibles par k si et seulement si est n/d%k+n%d%kévalué à 0 , ce qui est testé en comparant le résultat avec 1 .

Puisqu'une partie des exigences est que les deux tranches doivent représenter des entiers positifs, la valeur de n%d est également comparée à 1 . Notez que 1 n'a pas de diviseurs premiers, donc la comparaison plus chère avec 0 n'est pas requise. Notez également que d <n garantit déjà que n/dsera évalué à un entier positif.

Enfin, il récursivement tous f(n,d,k+1)(en essayant le diviseur commun potentiel suivant) et f(n,10*d)(en essayant le fractionnement) et renvoie le OU logique des trois résultats. Cela signifie que f renverra True si (et seulement si) k est un diviseur commun de n / d et n% d ou la même chose est vraie pour une plus grande valeur de k et / ou une puissance plus élevée de dix d .