Tous les défis
Moyen 0 résolus 0 % de réussite

Nombre triangulaire très divisible

Trouver le premier nombre triangulaire qui a au moins d diviseurs.

Ce que vous allez apprendre

  • Compter les diviseurs à partir de la décomposition en facteurs premiers
  • Utiliser la formule des nombres triangulaires
  • Séparer un produit de facteurs premiers entre eux

Problème

Les nombres triangulaires comptent les points d'un triangle formé de lignes de 1, 2, 3, ... points : T(1) = 1, T(2) = 3, T(3) = 6 et T(k) = k(k + 1) / 2. Parcourez-les dans l'ordre et arrêtez-vous au premier qui possède au moins d diviseurs positifs (1 et le nombre lui-même comptent).

Implémentez highly_divisible_triangular(d).

Compter les diviseurs un par un est trop lent pour les grands cas. Utilisez plutôt la décomposition en facteurs premiers : si n = p^a × q^b × ..., alors n a (a + 1)(b + 1)... diviseurs. Comme k et k + 1 sont premiers entre eux, vous pouvez les décomposer séparément.

Entrée

d : le nombre de diviseurs demandé.

Sortie

Renvoyez le premier nombre triangulaire qui a au moins d diviseurs.

Contraintes

1 ≤ d ≤ 300

Exemples

Exemple 1
Entrée :
d = 4

Sortie attendue :
expected = 6
Entrée :
long long d = 4;

Sortie attendue :
long long expected = 6;
Entrée :
long d = 4;

Sortie attendue :
long expected = 6;

Explication

1 a un seul diviseur et 3 en a deux, mais 6 en a quatre (1, 2, 3, 6), donc la réponse est 6.

Exemple 2
Entrée :
d = 9

Sortie attendue :
expected = 36
Entrée :
long long d = 9;

Sortie attendue :
long long expected = 36;
Entrée :
long d = 9;

Sortie attendue :
long expected = 36;

Explication

28 a six diviseurs et 36 = 2² × 3² en a 3 × 3 = 9 (1, 2, 3, 4, 6, 9, 12, 18, 36), donc la réponse est 36.

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

T(k) = k(k + 1) / 2, et k et k + 1 n'ont aucun facteur commun.

Indice 2

Divisez par deux celui des deux nombres k et k + 1 qui est pair, puis comptez les diviseurs de chaque partie.

Indice 3

Le nombre de diviseurs d'un produit de nombres premiers entre eux est le produit de leurs nombres de diviseurs.

Complexité attendue

temps O(K √K) pour K nombres triangulaires testés, espace supplémentaire O(1)

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.