Le plus grand facteur premier des nombres voisins

13

Je pense qu'il est plus facile d'expliquer ce défi de manière séquentielle. Commencez par un numéro d'entrée N et:

  1. Trouvez son facteur premier le plus élevé
  2. Vérifiez les numéros ci - dessus et au- dessous N et voir si le plus grand facteur premier est plus élevé (le plus grand facteur premier de N-1 et / ou N + 1 est supérieur au facteur de N .
  3. Continuez à vérifier les nombres supérieurs et / ou inférieurs voisins de N dans les directions où les facteurs les plus élevés augmentent ( (N-2, N-3 ...) et / ou (N + 2, N + 3 ...) , etc. sur)
  4. Une fois qu'il n'y a aucun facteur premier dans l'une ou l'autre direction qui soit supérieur à ceux que nous avons déjà trouvés, nous nous arrêtons et produisons le facteur premier le plus élevé que nous ayons rencontré.

Regardons un exemple:

245a les facteurs premiers 5, 7, 7. Ses voisins sont:

244 -> 2,  2,  61
245 -> 5,  7,  7
246 -> 2,  3,  41

Le facteur premier le plus élevé augmente dans les deux sens, nous devons donc regarder le prochain voisin:

243 -> 3,   3,  3,  3,  3
244 -> 2,   2,  2,  61
245 -> 5,   7,  7
246 -> 2,   3,  41
247 -> 13,  19

Les facteurs premiers les plus élevés diminuent maintenant dans les deux sens, donc le facteur premier le plus élevé que nous avons rencontré est 61et devrait donc être renvoyé.

Un autre exemple:

Regardons 1024. Ses principaux facteurs sont 2, 2, 2, 2, 2, 2, 2, 2, 2, 2. Les facteurs premiers de ses voisins les plus proches sont:

1023 -> 3, 11, 31
1024 -> 2,  2,  2,  2,  2,  2,  2,  2,  2,  2
1025 -> 5,  5, 41

Les facteurs premiers les plus élevés augmentent dans les deux sens, de 2à 31ou 41. Regardons les voisins:

1022 -> 2, 7,  73
1023 -> 3, 11, 31
1024 -> 2,  2,  2,  2,  2,  2,  2,  2,  2,  2
1025 -> 5,  5, 41
1026 -> 2,  3,  3, 19

Le facteur premier le plus élevé pour 1022est 73et le facteur premier le plus élevé pour 1026est 19. Puisque 19c'est plus bas que 41ça ne nous intéresse pas. Il continue d'augmenter pour des nombres inférieurs à N, nous allons donc vérifier le suivant dans cette direction :

1021 -> 1021
1022 -> 2, 7,  73
1023 -> 3, 11, 31
1024 -> 2,  2,  2,  2,  2,  2,  2,  2,  2,  2
1025 -> 5,  5, 41
1026 -> 2,  3,  3, 19

1021 est un nombre premier et le plus haut niveau que nous ayons rencontré, il doit donc être renvoyé.

Règles:

  • Vous n'obtiendrez que des valeurs positives Nsupérieures à 1et inférieures à 2^31-2.
  • Les formats d'entrée et de sortie sont facultatifs, mais les chiffres doivent être en base 10.
  • Vous devez continuer à rechercher des nombres premiers plus élevés tant que la valeur la plus élevée augmente dans cette direction. Les directions sont indépendantes les unes des autres.

Cas de test:

Format: N, highest_factor

2, 3
3, 3
6, 7
8, 11
24, 23 
1000, 997
736709, 5417 
8469038, 9431
Stewie Griffin
la source
Disons que nous obtenons un facteur premier le plus élevé de 2N. Nous obtenons alors 5pour N-1 et 61pour N + 1. On obtient alors 19N-2 et 67N + 2. Faut-il continuer à essayer des nombres plus bas, depuis 19>5ou arrêter, depuis 5<61? C'est-à-dire que les maxima sont conservés de chaque côté? (Je ne sais pas si l'exemple est mathématiquement possible.)
PurkkaKoodari
@ Pietu1998, la question est-elle plus claire maintenant?
Stewie Griffin
N=2semble en fait être un cas de bord puisqu'il 1n'a pas de facteurs premiers, donc pas de facteur premier maximum avec lequel nous pouvons comparer afin de décider si nous devons continuer.
Jonathan Allan

Réponses:

4

Mathematica, 82 74 octets

Merci à Martin Ender pour avoir économisé 8 octets!

Max@@(±n_:=#//.x_/;l[t=x+n]>l@x:>t;l=FactorInteger[#][[-1,1]]&)/@{±-1,±1}&

Fonction sans nom prenant une entrée entière et retournant un entier.

±n_:=#//.x_/;l[t=x+n]>l@x:>tdéfinit une fonction unaire ±qui continue d'augmenter l'entrée entière de la fonction globale ntant que le plus grand facteur premier augmente. (La fonction du plus grand facteur premier est définie par l=FactorInteger[#][[-1,1]]&.) {±-1,±1}Applique donc cette fonction deux fois à l'entier d'entrée, avec incrément -1et à nouveau avec incrément 1. Ensuite, Max@@(...l...)/@...prend le plus grand des deux plus grands facteurs premiers ainsi trouvés.

Soumission précédente:

Max@@(l=FactorInteger[#][[-1,1]]&)/@(#//.x_/;l[t=x+#2]>l[x]:>t&@@@{{#,-1},{#,1}})&
Greg Martin
la source
Enregistré quelques octets en évitant le @@@(et vous pouvez l'utiliser l@xici):Max@@(±n_:=#//.x_/;l[t=x+n]>l@x:>t;l=FactorInteger[#][[-1,1]]&)/@{±-1,±1}&
Martin Ender
1

Perl, 137 octets

122 octets de code + 15 octets pour -pet -Mntheory=:all.

sub f{$t=(factor$_+pop)[-1]}$i=$j=1;while($i|$j){f++$c;($i&=$t>$h)&&($h=$t);f-$c;($j&=$t>$l)&&($l=$t)}$_=$h>$l?$h:$l?$l:$_

Pour l'exécuter:

perl -pMntheory=:all -e 'sub f{$t=(factor$_+pop)[-1]}$i=$j=1;while($i|$j){f++$c;($i&=$t>$h)&&($h=$t);f-$c;($j&=$t>$l)&&($l=$t)}$_=$h>$l?$h:$l?$l:$_' <<< 736709

Si vous ne l'avez pas ntheoryinstallé, vous pouvez l'installer en tapant (echo y;echo) | perl -MCPAN -e 'install ntheory'votre terminal.

Dada
la source
0

Rubis, 99 octets

->n{f=->n{i=2;n%i<1?n/=i:i+=1while i<n;n};g=->s,z{s+=z while f[s+z]>b=f[s];b};[g[n,1],g[n,-1]].max}

Explication:

  • f () est le facteur premier le plus élevé
  • g () est la fonction de recherche de voisins dans une direction
  • appliquer g à (n, -1) et à (n, + 1) pour rechercher dans les deux directions
GB
la source