C# fonction qui accepte entier n et revenir plus petit nombre qui peut diviser les numéros 1..n

Question 1

J'ai besoin d'écrire une fonction qui prend comme argument le numéro n et retour (string) le plus petit numéro disponible qui permet de diviser par tous les nombres de 1 à n. exemple, si n=4, alors la fonction retourne 12 12/4 12/3 12/1 12/2 sont des nombres entiers.

j'ai écrit une fonction qui fonctionne très bien lorsque les nombres sont de moins de 19.. au-dessus de 19 le temps de calcul devient de plus en plus. quelqu'un peut-il me donner un indice de la façon de mieux le mécanisme de cette fonction pour le faire plus rapidement

 public static string Smallest(int n)
        {
           
            int good = 0;//will hold number of times we got divide with no remianders
            int num = n;//smallest possible number is n
            while (true)
            {
                good = 0;
                for (int i=n; i>=1; i--)
                {
                    if (num % i ==0) good++;//meaning we got zero remainder for the divide
                    if (good == n) return num.ToString();//num of times we got zero remainders == n.

                }
                num++;
            }

        }

Question 2

Vous allez avoir d'énormes numéros pour les grands nc'est pourquoi nous allons utiliser BigInteger à l'intérieur de calcul. Comme Abhishek Pandey, on doit calculer LCMqui peut être obtenu comme

 LCM(a, b) = a * b / GCD(a, b)

où DMC est le Plus grand Diviseur Commun

Code:

using System.Numerics;

...

public static string Smallest(int n) {
  if (n < 1)
    throw new ArgumentOutOfRangeException(nameofn()); 

  BigInteger result = 1;

  for (int i = 1; i <= n; ++i) 
    result = result * i / BigInteger.GreatestCommonDivisor(result, i);

  return result.ToString();
}

Démo:

  using System.Linq;
  using System.Numerics;

  ...

  var demos = string.Join(Environment.NewLine, Enumerable
    .Range(1, 20)
    .Select(n => $"{n,2} : {Smallest(n),20}"));

  Console.WriteLine(demos);
  Console.WriteLine();
  Console.WriteLine(Smallest(100));

Résultat:

 1 :                    1
 2 :                    2
 3 :                    6
 4 :                   12
 5 :                   60
 6 :                   60
 7 :                  420
 8 :                  840
 9 :                 2520
10 :                 2520
11 :                27720
12 :                27720
13 :               360360
14 :               360360
15 :               360360
16 :               720720
17 :             12252240
18 :             12252240
19 :            232792560
20 :            232792560

69720375229712477164533808935312303556800

Question 3

Ma logique:

Nous prenons un certain nombre de - c'est un nombre minimum de ce qui peut être retourné
numéro 1 - si elle ne peut pas diviser par pas de rappel ajouter à la n initiale n

N'oubliez pas de mettre à jour le nombre initial lors de l'étape 2 a rappel

Faites cela jusqu'à ce que vous obtenez la valeur correcte

Question 4

Vous devez trouver le PPCM (plus petit Commun Multiple) de tous les nombres de 1 to n.

Voici un bon exemple de trouver LCM d'un tableau d'éléments. https://www.geeksforgeeks.org/lcm-of-given-array-elements/

Vous pouvez créer un tableau de tous les nombres de 1 à n et de le passer à cette fonction.

OU

Vous pouvez la modifier pour ne laisser passer que n et de le rendre efficace pour votre cas d'utilisation.

Dmitry Bychenko · Answer 1 · 2021-11-23T18:37:03

Vous allez avoir d'énormes numéros pour les grands nc'est pourquoi nous allons utiliser BigInteger à l'intérieur de calcul. Comme Abhishek Pandey, on doit calculer LCMqui peut être obtenu comme

 LCM(a, b) = a * b / GCD(a, b)

où DMC est le Plus grand Diviseur Commun

Code:

using System.Numerics;

...

public static string Smallest(int n) {
  if (n < 1)
    throw new ArgumentOutOfRangeException(nameofn()); 

  BigInteger result = 1;

  for (int i = 1; i <= n; ++i) 
    result = result * i / BigInteger.GreatestCommonDivisor(result, i);

  return result.ToString();
}

Démo:

  using System.Linq;
  using System.Numerics;

  ...

  var demos = string.Join(Environment.NewLine, Enumerable
    .Range(1, 20)
    .Select(n => $"{n,2} : {Smallest(n),20}"));

  Console.WriteLine(demos);
  Console.WriteLine();
  Console.WriteLine(Smallest(100));

Résultat:

 1 :                    1
 2 :                    2
 3 :                    6
 4 :                   12
 5 :                   60
 6 :                   60
 7 :                  420
 8 :                  840
 9 :                 2520
10 :                 2520
11 :                27720
12 :                27720
13 :               360360
14 :               360360
15 :               360360
16 :               720720
17 :             12252240
18 :             12252240
19 :            232792560
20 :            232792560

69720375229712477164533808935312303556800

Andrew · Answer 2 · 2021-11-23T18:29:42

Ma logique:

Nous prenons un certain nombre de - c'est un nombre minimum de ce qui peut être retourné
numéro 1 - si elle ne peut pas diviser par pas de rappel ajouter à la n initiale n

N'oubliez pas de mettre à jour le nombre initial lors de l'étape 2 a rappel

Faites cela jusqu'à ce que vous obtenez la valeur correcte

Abhishek Pandey · Answer 3 · 2021-11-23T18:22:57

Vous devez trouver le PPCM (plus petit Commun Multiple) de tous les nombres de 1 to n.

Voici un bon exemple de trouver LCM d'un tableau d'éléments. https://www.geeksforgeeks.org/lcm-of-given-array-elements/

Vous pouvez créer un tableau de tous les nombres de 1 à n et de le passer à cette fonction.

OU

Vous pouvez la modifier pour ne laisser passer que n et de le rendre efficace pour votre cas d'utilisation.

C# fonction qui accepte entier n et revenir plus petit nombre qui peut diviser les numéros 1..n

La question

La meilleure réponse

Dans d'autres langues

Cette page est dans d'autres langues

Populaires dans cette catégorie

Questions populaires dans cette catégorie