Dado un número natural cuadrado perfecto N . La tarea es encontrar todos los factores de N .
Ejemplos
Entrada: N = 100
Salida: 1 2 4 5 10 20 25 50 100Entrada: N = 900
Salida: 1 2 4 3 6 12 9 18 36 5 10 20 15 30 60 45 90 180 25 50 100 75 150 300 225 450 900
Acercarse:
- Encuentre la raíz cuadrada de N en temp.
- Encuentre todos los factores primos de la temperatura en O(sqrt(temp)) usando el enfoque discutido en este artículo.
- Inicialice un factor de array [] con el elemento 1 en él.
- Almacene todos los factores primos de la temperatura obtenidos en el paso anterior dos veces en una array factor[] .
- Inicialice una array M tal que para cada elemento en factor[] a partir del índice 1:
- Si factor[i] es igual a factor[i-1] , almacene factor[i]*factor[i-1] en la array M en la fila i – 1 .
- De lo contrario factor[i] no es igual a factor[i-1] , luego almacene factor[i]*factor[i-1] en la array M en la fila i .
- Si factor[i] es igual a factor[i-1] , almacene factor[i]*factor[i-1] en la array M en la fila i – 1 .
- Inicialice dos arrays arr1[] y arr2[] con el elemento 1 en ambas arrays.
- Iterar sobre cada fila de la array M de modo que el producto de cada elemento en arr1[] con cada elemento de la fila actual debe almacenarse en arr2[] .
- Después del paso anterior, copie todos los elementos de arr2[] en arr1[].
- Repita los dos pasos anteriores, hasta que todo el elemento de la array M sea transversal.
- La array arr2[] contiene todos los factores del número N.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the factors
// of large perfect square number
// in O(sqrt(sqrt(N))) time
#include "bits/stdc++.h"
using namespace std;
int MAX = 100000;
// Function that find all the prime
// factors of N
void findFactors(int N)
{
// Store the sqrt(N) in temp
int temp = sqrt(N);
// Initialise factor array with
// 1 as a factor in it
int factor[MAX] = { 1 };
int i, j, k;
int len1 = 1;
// Check divisibility by 2
while (temp % 2 == 0) {
// Store the factors twice
factor[len1++] = 2;
factor[len1++] = 2;
temp /= 2;
}
// Check for other prime
// factors other than 2
for (j = 3; j < sqrt(temp); j += 2) {
// If j is a prime factor
while (temp % j == 0) {
// Store the prime
// factor twice
factor[len1++] = j;
factor[len1++] = j;
temp /= j;
}
}
// If j is prime number left
// other than 2
if (temp > 2) {
// Store j twice
factor[len1++] = temp;
factor[len1++] = temp;
}
// Initialise Matrix M to
// to store all the factors
int M[len1][MAX] = { 0 };
// tpc for rows
// tpr for column
int tpc = 0, tpr = 0;
// Initialise M[0][0] = 1 as
// it also factor of N
M[0][0] = 1;
j = 1;
// Traversing factor array
while (j < len1) {
// If current and previous
// factors are not same then
// move to next row and
// insert the current factor
if (factor[j] != factor[j - 1]) {
tpr++;
M[tpr][0] = factor[j];
j++;
tpc = 1;
}
// If current and previous
// factors are same then,
// Insert the factor with
// previous factor inserted
// in matrix M
else {
M[tpr][tpc]
= M[tpr][tpc - 1] * factor[j];
j++;
tpc++;
}
}
// The arr1[] and arr2[] used to
// store all the factors of N
int arr1[MAX], arr2[MAX];
int l1, l2;
l1 = l2 = 1;
// Initialise arrays as 1
arr1[0] = arr2[0] = 1;
// Traversing the matrix M
for (i = 1; i < tpr + 1; i++) {
// Traversing till column
// element doesn't become 0
for (j = 0; M[i][j] != 0; j++) {
// Store the product of
// every element of current
// row with every element
// in arr1[]
for (k = 0; k < l1; k++) {
arr2[l2++]
= arr1[k] * M[i][j];
}
}
// Copying every element of
// arr2[] in arr1[]
for (j = l1; j < l2; j++) {
arr1[j] = arr2[j];
}
// length of arr2[] and arr1[]
// are equal after copying
l1 = l2;
}
// Print all the factors
for (i = 0; i < l2; i++) {
cout << arr2[i] << ' ';
}
}
// Drivers Code
int main()
{
int N = 900;
findFactors(N);
return 0;
}
Java
// Java program to find the factors
// of large perfect square number
// in O(Math.sqrt(Math.sqrt(N))) time
import java.util.*;
class GFG{
static int MAX = 100000;
// Function that find all the prime
// factors of N
static void findFactors(int N)
{
// Store the Math.sqrt(N) in temp
int temp = (int) Math.sqrt(N);
// Initialise factor array with
// 1 as a factor in it
int []factor = new int[MAX];
Arrays.fill(factor, 1);
int i, j, k;
int len1 = 1;
// Check divisibility by 2
while (temp % 2 == 0) {
// Store the factors twice
factor[len1++] = 2;
factor[len1++] = 2;
temp /= 2;
}
// Check for other prime
// factors other than 2
for (j = 3; j < Math.sqrt(temp); j += 2) {
// If j is a prime factor
while (temp % j == 0) {
// Store the prime
// factor twice
factor[len1++] = j;
factor[len1++] = j;
temp /= j;
}
}
// If j is prime number left
// other than 2
if (temp > 2) {
// Store j twice
factor[len1++] = temp;
factor[len1++] = temp;
}
// Initialise Matrix M to
// to store all the factors
int [][]M = new int[len1][MAX];
// tpc for rows
// tpr for column
int tpc = 0, tpr = 0;
// Initialise M[0][0] = 1 as
// it also factor of N
M[0][0] = 1;
j = 1;
// Traversing factor array
while (j < len1) {
// If current and previous
// factors are not same then
// move to next row and
// insert the current factor
if (factor[j] != factor[j - 1]) {
tpr++;
M[tpr][0] = factor[j];
j++;
tpc = 1;
}
// If current and previous
// factors are same then,
// Insert the factor with
// previous factor inserted
// in matrix M
else {
M[tpr][tpc]
= M[tpr][tpc - 1] * factor[j];
j++;
tpc++;
}
}
// The arr1[] and arr2[] used to
// store all the factors of N
int []arr1 = new int[MAX];
int []arr2 = new int[MAX];
int l1, l2;
l1 = l2 = 1;
// Initialise arrays as 1
arr1[0] = arr2[0] = 1;
// Traversing the matrix M
for (i = 1; i < tpr + 1; i++) {
// Traversing till column
// element doesn't become 0
for (j = 0; M[i][j] != 0; j++) {
// Store the product of
// every element of current
// row with every element
// in arr1[]
for (k = 0; k < l1; k++) {
arr2[l2++]
= arr1[k] * M[i][j];
}
}
// Copying every element of
// arr2[] in arr1[]
for (j = l1; j < l2; j++) {
arr1[j] = arr2[j];
}
// length of arr2[] and arr1[]
// are equal after copying
l1 = l2;
}
// Print all the factors
for (i = 0; i < l2; i++) {
System.out.print(arr2[i] + " ");
}
}
// Drivers Code
public static void main(String[] args)
{
int N = 900;
findFactors(N);
}
}
// This code is contributed by sapnasingh4991
Python3
# Python 3 program to find the factors
# of large perfect square number
# in O(sqrt(sqrt(N))) time
import math
MAX = 100000
# Function that find all the prime
# factors of N
def findFactors( N):
# Store the sqrt(N) in temp
temp = int(math.sqrt(N))
# Initialise factor array with
# 1 as a factor in it
factor = [1]*MAX
len1 = 1
# Check divisibility by 2
while (temp % 2 == 0) :
# Store the factors twice
factor[len1] = 2
len1 += 1
factor[len1] = 2
len1 += 1
temp //= 2
# Check for other prime
# factors other than 2
sqt = math.sqrt(temp)
for j in range(3, math.ceil(sqt), 2):
# If j is a prime factor
while (temp % j == 0):
# Store the prime
# factor twice
factor[len1] = j
len1 += 1
factor[len1] = j
len1 += 1
temp //= j
# If j is prime number left
# other than 2
if (temp > 2) :
# Store j twice
factor[len1] = temp
len1 += 1
factor[len1] = temp
len1 += 1
# Initialise Matrix M to
# to store all the factors
M = [ [ 0 for x in range(MAX)] for y in range(len1)]
# tpc for rows
# tpr for column
tpc , tpr = 0 , 0
# Initialise M[0][0] = 1 as
# it also factor of N
M[0][0] = 1
j = 1
# Traversing factor array
while (j < len1):
# If current and previous
# factors are not same then
# move to next row and
# insert the current factor
if (factor[j] != factor[j - 1]):
tpr+=1
M[tpr][0] = factor[j]
j += 1
tpc = 1
# If current and previous
# factors are same then,
# Insert the factor with
# previous factor inserted
# in matrix M
else :
M[tpr][tpc]= M[tpr][tpc - 1] * factor[j]
j += 1
tpc += 1
# The arr1[] and arr2[] used to
# store all the factors of N
arr1 = [0]*MAX
arr2 = [0]*MAX
l1 = l2 = 1
# Initialise arrays as 1
arr1[0] = 1
arr2[0] = 1
# Traversing the matrix M
# print("tpr ",tpr)
for i in range(1 , tpr + 1) :
# Traversing till column
# element doesn't become 0
j = 0
while M[i][j] != 0:
# Store the product of
# every element of current
# row with every element
# in arr1[]
for k in range(l1):
arr2[l2]= arr1[k] * M[i][j]
l2 += 1
j += 1
# Copying every element of
# arr2[] in arr1[]
for j in range(l1, l2):
arr1[j] = arr2[j]
# length of arr2[] and arr1[]
# are equal after copying
l1 = l2
# Print all the factors
for i in range(l2):
print(arr2[i] ,end= " ")
# Drivers Code
if __name__ == "__main__":
N = 900
findFactors(N)
# This code is contributed by chitranayal
C#
// C# program to find the factors
// of large perfect square number
// in O(Math.Sqrt(Math.Sqrt(N))) time
using System;
class GFG{
static int MAX = 100000;
// Function that find all the prime
// factors of N
static void findFactors(int N)
{
// Store the Math.Sqrt(N) in temp
int temp = (int) Math.Sqrt(N);
// Initialise factor array with
// 1 as a factor in it
int []factor = new int[MAX];
for(int l= 0; l < MAX; l++)
factor[l] = 1;
int i, j, k;
int len1 = 1;
// Check divisibility by 2
while (temp % 2 == 0) {
// Store the factors twice
factor[len1++] = 2;
factor[len1++] = 2;
temp /= 2;
}
// Check for other prime
// factors other than 2
for (j = 3; j < Math.Sqrt(temp); j += 2) {
// If j is a prime factor
while (temp % j == 0) {
// Store the prime
// factor twice
factor[len1++] = j;
factor[len1++] = j;
temp /= j;
}
}
// If j is prime number left
// other than 2
if (temp > 2) {
// Store j twice
factor[len1++] = temp;
factor[len1++] = temp;
}
// Initialise Matrix M to
// to store all the factors
int [,]M = new int[len1, MAX];
// tpc for rows
// tpr for column
int tpc = 0, tpr = 0;
// Initialise M[0,0] = 1 as
// it also factor of N
M[0, 0] = 1;
j = 1;
// Traversing factor array
while (j < len1) {
// If current and previous
// factors are not same then
// move to next row and
// insert the current factor
if (factor[j] != factor[j - 1]) {
tpr++;
M[tpr, 0] = factor[j];
j++;
tpc = 1;
}
// If current and previous
// factors are same then,
// Insert the factor with
// previous factor inserted
// in matrix M
else {
M[tpr,tpc]
= M[tpr,tpc - 1] * factor[j];
j++;
tpc++;
}
}
// The arr1[] and arr2[] used to
// store all the factors of N
int []arr1 = new int[MAX];
int []arr2 = new int[MAX];
int l1, l2;
l1 = l2 = 1;
// Initialise arrays as 1
arr1[0] = arr2[0] = 1;
// Traversing the matrix M
for (i = 1; i < tpr + 1; i++) {
// Traversing till column
// element doesn't become 0
for (j = 0; M[i, j] != 0; j++) {
// Store the product of
// every element of current
// row with every element
// in arr1[]
for (k = 0; k < l1; k++) {
arr2[l2++]
= arr1[k] * M[i, j];
}
}
// Copying every element of
// arr2[] in arr1[]
for (j = l1; j < l2; j++) {
arr1[j] = arr2[j];
}
// length of arr2[] and arr1[]
// are equal after copying
l1 = l2;
}
// Print all the factors
for (i = 0; i < l2; i++) {
Console.Write(arr2[i] + " ");
}
}
// Drivers Code
public static void Main(String[] args)
{
int N = 900;
findFactors(N);
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// Javascript program to find the factors
// of large perfect square number
// in O(Math.sqrt(Math.sqrt(N))) time
let MAX = 100000;
// Function that find all the prime
// factors of N
function findFactors(N)
{
// Store the Math.sqrt(N) in temp
let temp = Math.floor(Math.sqrt(N));
// Initialise factor array with
// 1 as a factor in it
let factor = new Array(MAX);
for(let i = 0; i < MAX; i++)
{
factor[i] = 1;
}
let i, j, k;
let len1 = 1;
// Check divisibility by 2
while (temp % 2 == 0)
{
// Store the factors twice
factor[len1++] = 2;
factor[len1++] = 2;
temp = Math.floor(temp / 2);
}
// Check for other prime
// factors other than 2
for(j = 3; j < Math.sqrt(temp); j += 2)
{
// If j is a prime factor
while (temp % j == 0)
{
// Store the prime
// factor twice
factor[len1++] = j;
factor[len1++] = j;
temp = Math.floor(temp / j);
}
}
// If j is prime number left
// other than 2
if (temp > 2)
{
// Store j twice
factor[len1++] = temp;
factor[len1++] = temp;
}
// Initialise Matrix M to
// to store all the factors
let M = new Array(len1);
for(let i = 0; i < len1; i++)
{
M[i] = new Array(MAX);
for(let j = 0; j < MAX; j++)
{
M[i][j] = 0;
}
}
// tpc for rows
// tpr for column
let tpc = 0, tpr = 0;
// Initialise M[0][0] = 1 as
// it also factor of N
M[0][0] = 1;
j = 1;
// Traversing factor array
while (j < len1)
{
// If current and previous
// factors are not same then
// move to next row and
// insert the current factor
if (factor[j] != factor[j - 1])
{
tpr++;
M[tpr][0] = factor[j];
j++;
tpc = 1;
}
// If current and previous
// factors are same then,
// Insert the factor with
// previous factor inserted
// in matrix M
else
{
M[tpr][tpc] = M[tpr][tpc - 1] * factor[j];
j++;
tpc++;
}
}
// The arr1[] and arr2[] used to
// store all the factors of N
let arr1 = new Array(MAX);
let arr2 = new Array(MAX);
for(let i = 0; i < MAX; i++)
{
arr1[i] = 0;
arr2[i] = 0;
}
let l1, l2;
l1 = l2 = 1;
// Initialise arrays as 1
arr1[0] = arr2[0] = 1;
// Traversing the matrix M
for(i = 1; i < tpr + 1; i++)
{
// Traversing till column
// element doesn't become 0
for(j = 0; M[i][j] != 0; j++)
{
// Store the product of
// every element of current
// row with every element
// in arr1[]
for(k = 0; k < l1; k++)
{
arr2[l2++] = arr1[k] * M[i][j];
}
}
// Copying every element of
// arr2[] in arr1[]
for(j = l1; j < l2; j++)
{
arr1[j] = arr2[j];
}
// length of arr2[] and arr1[]
// are equal after copying
l1 = l2;
}
// Print all the factors
for(i = 0; i < l2; i++)
{
document.write(arr2[i] + " ");
}
}
// Driver Code
let N = 900;
findFactors(N);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
1 2 4 3 6 12 9 18 36 5 10 20 15 30 60 45 90 180 25 50 100 75 150 300 225 450 900
Complejidad del tiempo: O(sqrt(sqrt(N)))
Espacio Auxiliar: O(MAX)
Publicación traducida automáticamente
Artículo escrito por epistler_999 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA