Как найти все множители натурального числа в C ++, Python и JavaScript
Фактор – это число, которое точно делит данное число; то есть делит число, не оставляя остатка. Определение множителей числа с помощью программирования может помочь вам укрепить ваши концепции циклов, условных операторов и операторов по модулю.
В этой статье вы узнаете, как найти все множители натурального числа с помощью C ++, Python и JavaScript.
Постановка задачи
Вы дали натуральное число пит, вам нужно найти и напечатать все различные факторы NUM.
Пример 1 : Пусть num = 60.
Множители 60: 1 2 3 4 5 6 10 12 15 20 30 60
Таким образом, на выходе получается 1 2 3 4 5 6 10 12 15 20 30 60.
Пример 2 : Пусть num = 100.
Множители 100: 1 2 4 5 10 20 25 50 100
Таким образом, на выходе получается 1 2 4 5 10 20 25 50 100.
Пример 3 : Пусть num = 85.
Множители 85: 1 5 17 85
Таким образом, на выходе получится 1 5 17 85.
Базовый подход к решению проблемы
Вы можете найти все различные факторы числа, следуя приведенному ниже подходу:
- Перебрать все числа от 1 до num .
- Если число полностью делит число , выведите число.
При таком подходе временная сложность решения будет O (n), а необходимое вспомогательное пространство – O (1).
Программа на C ++ для поиска множителей числа
Ниже приведена программа на C ++ для поиска всех факторов числа:
// 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;
}Выход:
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Программа Python для поиска множителей в числах
Ниже приведена программа Python для поиска всех факторов числа:
# 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)
Выход:
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
Программа на JavaScript для поиска множителей в числах
Ниже приведена программа на JavaScript, чтобы найти все факторы числа:
// 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);Выход:
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
Оптимизированный подход к решению проблемы
Если вы посмотрите на множители числа, они появятся парами. Например, если num = 64, множители 64 будут: (1, 64), (2, 32), (4, 16) и (8, 8). Вы можете использовать этот факт для оптимизации своего решения.
Однако в случае двух равных множителей вам нужно вывести множитель только один раз. Как и в приведенном выше примере, (8, 8) – два равных фактора. Так что распечатать их нужно только один раз.
Таким образом, вы можете использовать следующий оптимизированный подход, чтобы найти все различные факторы числа:
- Итерация все числа от 1 до квадратного корня из NUM.
- Если число идеально делит число , это означает, что число является делителем числа .
- Теперь проверьте, равен ли второй множитель ( число / 1-ый множитель) первому множителю.
- Если оба множителя равны, выведите множитель один раз.
- Если оба фактора не равны, выведите оба фактора.
При использовании этого подхода временная сложность решения составляет O (sqrt (n)), а необходимое вспомогательное пространство – O (1).
Программа на C ++, использующая оптимизированный подход к поиску множителей числа
Ниже приведена программа на C ++ для поиска всех факторов числа:
// 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;
}Выход:
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
Программа Python, использующая оптимизированный подход для поиска множителей числа
Ниже приведена программа Python для поиска всех факторов числа:
# 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)
Выход:
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Программа на JavaScript, использующая оптимизированный подход для поиска множителей числа
Ниже приведена программа на JavaScript, чтобы найти все факторы числа:
// 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);Выход:
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Понять основные принципы программирования
Как программисту очень важно понимать основные принципы программирования, такие как KISS (Keep It Simple, Stupid), DRY (Don't Repeat Yourself), Single Responsibility, YAGNI (Вам это не понадобится), Open / Closed, Композиция вместо наследования и т. Д.
Следование основным принципам программирования в конечном итоге сделает вас лучшим программистом.