Como encontrar todos os fatores de um número natural em C ++, Python e JavaScript

gurinho

Um fator é um número que divide um determinado número exatamente; ou seja, ele divide o número sem deixar resto. Encontrar os fatores de um número com a ajuda da programação pode ajudá-lo a solidificar seus conceitos de loops, instruções condicionais e operadores de módulo.

Neste artigo, você aprenderá como encontrar todos os fatores de um número natural usando C ++, Python e JavaScript.

Declaração do Problema

Você recebe um número natural num , você precisa encontrar e imprimir todos os fatores distintos de num .

Exemplo 1 : Seja num = 60.

Os fatores de 60 são: 1 2 3 4 5 6 10 12 15 20 30 60

Assim, a saída é 1 2 3 4 5 6 10 12 15 20 30 60.

Exemplo 2 : Seja num = 100.

Os fatores de 100 são: 1 2 4 5 10 20 25 50 100

Assim, a saída é 1 2 4 5 10 20 25 50 100.

Exemplo 3 : Seja num = 85.

Os fatores de 85 são: 1 5 17 85

Portanto, a saída é 1 5 17 85.

Abordagem básica para resolver o problema

Você pode encontrar todos os fatores distintos de um número seguindo a abordagem abaixo:

  1. Repita todos os números de 1 a num .
  2. Se o número divide perfeitamente num , imprima o número.

Usando esta abordagem, a complexidade de tempo da solução seria O (n) e o espaço auxiliar necessário seria O (1).

Programa C ++ para encontrar fatores de um número

Abaixo está o programa C ++ para encontrar todos os fatores de um número:

 // C++ program to find all factors of a natural number
 #include <iostream>
 using namespace std;
 void findFactors(int num)
 {
 for(int i=1; i<=num; i++)
 {
 if(num%i == 0)
 {
 cout << i << " ";
 }
 }
 cout << endl;
 }
 int main()
 {
 int num1 = 60;
 cout << "Factors of " << num1 << " are: " << endl;
 findFactors(num1);
 int num2 = 100;
 cout << "Factors of " << num2 << " are: " << endl;
 findFactors(num2);
 int num3 = 85;
 cout << "Factors of " << num3 << " are: " << endl;
 findFactors(num3);
 int num4 = 66;
 cout << "Factors of " << num4 << " are: " << endl;
 findFactors(num4);
 int num5 = 71;
 cout << "Factors of " << num5 << " are: " << endl;
 findFactors(num5);
 return 0;
 }

Saída:

 Factors of 60 are:
 1 2 3 4 5 6 10 12 15 20 30 60
 Factors of 100 are:
 1 2 4 5 10 20 25 50 100
 Factors of 85 are:
 1 5 17 85
 Factors of 66 are:
 1 2 3 6 11 22 33 66
 Factors of 71 are:
 1 71

Programa Python para encontrar fatores de um número

Abaixo está o programa Python para encontrar todos os fatores de um número:

 # Python program to find all factors of a natural number
 def findFactors(num):
 for i in range(1,num+1):
 if (num%i==0):
 print(i, end=" ")
 print()
 num1 = 60
 print("Factors of", num1, "are:")
 findFactors(num1)
 num2 = 100
 print("Factors of", num2, "are:")
 findFactors(num2)
 num3 = 85
 print("Factors of", num3, "are:")
 findFactors(num3)
 num4 = 66
 print("Factors of", num4, "are:")
 findFactors(num4)
 num5 = 71
 print("Factors of", num5, "are:")
 findFactors(num5)

Saída:

 Factors of 60 are:
 1 2 3 4 5 6 10 12 15 20 30 60
 Factors of 100 are:
 1 2 4 5 10 20 25 50 100
 Factors of 85 are:
 1 5 17 85
 Factors of 66 are:
 1 2 3 6 11 22 33 66
 Factors of 71 are:
 1 71

Relacionado: Como Encontrar o LCM e GCD de Dois Números em Vários Idiomas

Programa JavaScript para encontrar fatores de um número

Abaixo está o programa JavaScript para encontrar todos os fatores de um número:

 // JavaScript program to find all factors of a natural number
 function findFactors(num) {
 for(let i=1; i<=num; i++) {
 if(num%i == 0) {
 document.write(i + " ");
 }
 }
 document.write("<br>");
 }

 let num1 = 60;
 document.write("Factors of " + num1 + " are: " + "<br>");
 findFactors(num1);
 let num2 = 100;
 document.write("Factors of " + num2 + " are: " + "<br>");
 findFactors(num2);
 let num3 = 85;
 document.write("Factors of " + num3 + " are: " + "<br>");
 findFactors(num3);
 let num4 = 66;
 document.write("Factors of " + num4 + " are: " + "<br>");
 findFactors(num4);
 let num5 = 71;
 document.write("Factors of " + num5 + " are: " + "<br>");
 findFactors(num5);

Saída:

 Factors of 60 are:
 1 2 3 4 5 6 10 12 15 20 30 60
 Factors of 100 are:
 1 2 4 5 10 20 25 50 100
 Factors of 85 are:
 1 5 17 85
 Factors of 66 are:
 1 2 3 6 11 22 33 66
 Factors of 71 are:
 1 71

Relacionado: Uma introdução ao algoritmo de classificação de mesclagem

Abordagem otimizada para resolver o problema

Se você observar os fatores de um número, eles aparecem aos pares. Por exemplo, se num = 64, os fatores de 64 seriam: (1, 64), (2, 32), (4, 16) e (8, 8). Você pode usar esse fato para otimizar sua solução.

No entanto, no caso de dois fatores iguais, você precisa imprimir o fator apenas uma vez. Como no exemplo acima, (8, 8) são dois fatores iguais. Portanto, você precisa imprimi-los apenas uma vez.

Assim, você pode usar a seguinte abordagem otimizada para encontrar todos os fatores distintos de um número:

  1. Repita todos os números de 1 à raiz quadrada de num .
  2. Se o número divide perfeitamente num , significa que o número é um fator de num .
  3. Agora verifique se o segundo fator ( num / 1º fator) é igual ao primeiro fator.
  4. Se ambos os fatores forem iguais, imprima o fator uma vez.
  5. Se ambos os fatores forem desiguais, imprima ambos os fatores.

Usando esta abordagem, a complexidade de tempo da solução é O (sqrt (n)) e o espaço auxiliar necessário é O (1).

Programa C ++ usando abordagem otimizada para encontrar fatores de um número

Abaixo está o programa C ++ para encontrar todos os fatores de um número:

 // C++ program to find all factors of a natural number
 #include <bits/stdc++.h>
 using namespace std;
 void findFactors(int num)
 {
 for(int i=1; i<=sqrt(num); i++)
 {
 if(num%i == 0)
 {
 if(num/i == i)
 {
 cout << i << " ";
 }
 else
 {
 cout << i << " " << num/i << " ";
 }
 }
 }
 cout << endl;
 }
 int main()
 {
 int num1 = 60;
 cout << "Factors of " << num1 << " are: " << endl;
 findFactors(num1);
 int num2 = 100;
 cout << "Factors of " << num2 << " are: " << endl;
 findFactors(num2);
 int num3 = 85;
 cout << "Factors of " << num3 << " are: " << endl;
 findFactors(num3);
 int num4 = 66;
 cout << "Factors of " << num4 << " are: " << endl;
 findFactors(num4);
 int num5 = 71;
 cout << "Factors of " << num5 << " are: " << endl;
 findFactors(num5);
 return 0;
 }

Saída:

 Factors of 60 are:
 1 60 2 30 3 20 4 15 5 12 6 10
 Factors of 100 are:
 1 100 2 50 4 25 5 20 10
 Factors of 85 are:
 1 85 5 17
 Factors of 66 are:
 1 66 2 33 3 22 6 11
 Factors of 71 are:
 1 71

Relacionado: Como reverter uma string em C ++, Python e JavaScript

Programa Python usando abordagem otimizada para encontrar fatores de um número

Abaixo está o programa Python para encontrar todos os fatores de um número:

 # Python program to find all factors of a natural number
 import math
 def findFactors(num):
 i = 1
 while i <= math.sqrt(num):
 if (num%i==0):
 if (num/i == i):
 print(i, end=" ")
 else:
 print(i, num//i, end=" ")
 i = i + 1
 print()
 num1 = 60
 print("Factors of", num1, "are:")
 findFactors(num1)
 num2 = 100
 print("Factors of", num2, "are:")
 findFactors(num2)
 num3 = 85
 print("Factors of", num3, "are:")
 findFactors(num3)
 num4 = 66
 print("Factors of", num4, "are:")
 findFactors(num4)
 num5 = 71
 print("Factors of", num5, "are:")
 findFactors(num5)

Saída:

 Factors of 60 are:
 1 60 2 30 3 20 4 15 5 12 6 10
 Factors of 100 are:
 1 100 2 50 4 25 5 20 10
 Factors of 85 are:
 1 85 5 17
 Factors of 66 are:
 1 66 2 33 3 22 6 11
 Factors of 71 are:
 1 71

Programa JavaScript usando abordagem otimizada para encontrar fatores de um número

Abaixo está o programa JavaScript para encontrar todos os fatores de um número:

 // JavaScript program to find all factors of a natural number
 function findFactors(num) {
 for(let i=1; i<=Math.sqrt(num); i++) {
 if(num%i == 0) {
 if (parseInt(num/i, 10) == i)
 {
 document.write(i + " ");
 } else {
 document.write(i + " " + parseInt(num/i, 10) + " ");
 }
 }
 }
 document.write("<br>");
 }

 let num1 = 60;
 document.write("Factors of " + num1 + " are: " + "<br>");
 findFactors(num1);
 let num2 = 100;
 document.write("Factors of " + num2 + " are: " + "<br>");
 findFactors(num2);
 let num3 = 85;
 document.write("Factors of " + num3 + " are: " + "<br>");
 findFactors(num3);
 let num4 = 66;
 document.write("Factors of " + num4 + " are: " + "<br>");
 findFactors(num4);
 let num5 = 71;
 document.write("Factors of " + num5 + " are: " + "<br>");
 findFactors(num5);

Saída:

 Factors of 60 are:
 1 60 2 30 3 20 4 15 5 12 6 10
 Factors of 100 are:
 1 100 2 50 4 25 5 20 10
 Factors of 85 are:
 1 85 5 17
 Factors of 66 are:
 1 66 2 33 3 22 6 11
 Factors of 71 are:
 1 71

Entenda os princípios básicos de programação

Como um programador, é muito importante entender os princípios básicos de programação como KISS (Keep It Simple, Stupid), DRY (Don't Repeat Yourself), Single Responsibility, YAGNI (Você não vai precisar disso), Open / Closed, Composição sobre herança, etc.

Seguir os princípios básicos de programação o tornará um programador melhor.