Dada una array de enteros. Estamos obligados a escribir un programa para imprimir el número de factores de cada elemento de la array dada.
Ejemplos:
Input: 10 12 14 Output: 4 6 4 Explanation: There are 4 factors of 10 (1, 2, 5, 10) and 6 of 12 and 4 of 14. Input: 100 1000 10000 Output: 9 16 25 Explanation: There are 9 factors of 100 and 16 of 1000 and 25 of 10000.
C++
// C++ program to count number of factors
// of an array of integers
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000001;
// array to store prime factors
int factor[MAX] = { 0 };
// function to generate all prime factors
// of numbers from 1 to 10^6
void generatePrimeFactors()
{
factor[1] = 1;
// Initializes all the positions with their value.
for (int i = 2; i < MAX; i++)
factor[i] = i;
// Initializes all multiples of 2 with 2
for (int i = 4; i < MAX; i += 2)
factor[i] = 2;
// A modified version of Sieve of Eratosthenes to
// store the smallest prime factor that divides
// every number.
for (int i = 3; i * i < MAX; i++) {
// check if it has no prime factor.
if (factor[i] == i) {
// Initializes of j starting from i*i
for (int j = i * i; j < MAX; j += i) {
// if it has no prime factor before, then
// stores the smallest prime divisor
if (factor[j] == j)
factor[j] = i;
}
}
}
}
// function to calculate number of factors
int calculateNoOfFactors(int n)
{
if (n == 1)
return 1;
int ans = 1;
// stores the smallest prime number
// that divides n
int dup = factor[n];
// stores the count of number of times
// a prime number divides n.
int c = 1;
// reduces to the next number after prime
// factorization of n
int j = n / factor[n];
// false when prime factorization is done
while (j != 1) {
// if the same prime number is dividing n,
// then we increase the count
if (factor[j] == dup)
c += 1;
/* if its a new prime factor that is factorizing n,
then we again set c=1 and change dup to the new
prime factor, and apply the formula explained
above. */
else {
dup = factor[j];
ans = ans * (c + 1);
c = 1;
}
// prime factorizes a number
j = j / factor[j];
}
// for the last prime factor
ans = ans * (c + 1);
return ans;
}
// Driver program to test above function
int main()
{
// generate prime factors of number
// upto 10^6
generatePrimeFactors();
int a[] = { 10, 30, 100, 450, 987 };
int q = sizeof(a) / sizeof(a[0]);
for (int i = 0; i < q; i++)
cout << calculateNoOFactors(a[i]) << " ";
return 0;
}
Java
// JAVA Code For Efficient program to print
// the number of factors of n numbers
import java.util.*;
class GFG {
static int MAX = 1000001;
static int factor[];
// function to generate all prime
// factors of numbers from 1 to 10^6
static void generatePrimeFactors()
{
factor[1] = 1;
// Initializes all the positions with
// their value.
for (int i = 2; i < MAX; i++)
factor[i] = i;
// Initializes all multiples of 2 with 2
for (int i = 4; i < MAX; i += 2)
factor[i] = 2;
// A modified version of Sieve of
// Eratosthenes to store the
// smallest prime factor that
// divides every number.
for (int i = 3; i * i < MAX; i++) {
// check if it has no prime factor.
if (factor[i] == i) {
// Initializes of j starting from i*i
for (int j = i * i; j < MAX; j += i) {
// if it has no prime factor
// before, then stores the
// smallest prime divisor
if (factor[j] == j)
factor[j] = i;
}
}
}
}
// function to calculate number of factors
static int calculateNoOfFactors(int n)
{
if (n == 1)
return 1;
int ans = 1;
// stores the smallest prime number
// that divides n
int dup = factor[n];
// stores the count of number of times
// a prime number divides n.
int c = 1;
// reduces to the next number after prime
// factorization of n
int j = n / factor[n];
// false when prime factorization is done
while (j != 1) {
// if the same prime number is dividing n,
// then we increase the count
if (factor[j] == dup)
c += 1;
/* if its a new prime factor that is
factorizing n, then we again set c=1
and change dup to the new prime factor,
and apply the formula explained
above. */
else {
dup = factor[j];
ans = ans * (c + 1);
c = 1;
}
// prime factorizes a number
j = j / factor[j];
}
// for the last prime factor
ans = ans * (c + 1);
return ans;
}
/* Driver program to test above function */
public static void main(String[] args)
{
// array to store prime factors
factor = new int[MAX];
factor[0] = 0;
// generate prime factors of number
// upto 10^6
generatePrimeFactors();
int a[] = { 10, 30, 100, 450, 987 };
int q = a.length;
for (int i = 0; i < q; i++)
System.out.print(calculateNoOFactors(a[i]) + " ");
}
}
// This code is contributed by Arnav Kr. Mandal.
Python3
# Python3 program to count # number of factors # of an array of integers MAX = 1000001; # array to store # prime factors factor = [0]*(MAX + 1); # function to generate all # prime factors of numbers # from 1 to 10^6 def generatePrimeFactors(): factor[1] = 1; # Initializes all the # positions with their value. for i in range(2,MAX): factor[i] = i; # Initializes all # multiples of 2 with 2 for i in range(4,MAX,2): factor[i] = 2; # A modified version of # Sieve of Eratosthenes # to store the smallest # prime factor that divides # every number. i = 3; while(i * i < MAX): # check if it has # no prime factor. if (factor[i] == i): # Initializes of j # starting from i*i j = i * i; while(j < MAX): # if it has no prime factor # before, then stores the # smallest prime divisor if (factor[j] == j): factor[j] = i; j += i; i+=1; # function to calculate # number of factors def calculateNoOfFactors(n): if (n == 1): return 1; ans = 1; # stores the smallest # prime number that # divides n dup = factor[n]; # stores the count of # number of times a # prime number divides n. c = 1; # reduces to the next # number after prime # factorization of n j = int(n / factor[n]); # false when prime # factorization is done while (j > 1): # if the same prime # number is dividing # n, then we increase # the count if (factor[j] == dup): c += 1; # if its a new prime factor # that is factorizing n, # then we again set c=1 and # change dup to the new prime # factor, and apply the formula # explained above. else: dup = factor[j]; ans = ans * (c + 1); c = 1; # prime factorizes # a number j = int(j / factor[j]); # for the last # prime factor ans = ans * (c + 1); return ans; # Driver Code if __name__ == "__main__": # generate prime factors # of number upto 10^6 generatePrimeFactors() a = [10, 30, 100, 450, 987] q = len(a) for i in range (0,q): print(calculateNoOFactors(a[i]),end=" ") # This code is contributed # by mits.
C#
// C# program to count number of factors
// of an array of integers
using System;
class GFG {
static int MAX = 1000001;
// array to store prime factors
static int[] factor;
// function to generate all prime
// factors of numbers from 1 to 10^6
static void generatePrimeFactors()
{
factor[1] = 1;
// Initializes all the positions
// with their value.
for (int i = 2; i < MAX; i++)
factor[i] = i;
// Initializes all multiples of
// 2 with 2
for (int i = 4; i < MAX; i += 2)
factor[i] = 2;
// A modified version of Sieve of
// Eratosthenes to store the
// smallest prime factor that
// divides every number.
for (int i = 3; i * i < MAX; i++)
{
// check if it has no prime
// factor.
if (factor[i] == i)
{
// Initializes of j
// starting from i*i
for (int j = i * i;
j < MAX; j += i)
{
// if it has no prime
// factor before, then
// stores the smallest
// prime divisor
if (factor[j] == j)
factor[j] = i;
}
}
}
}
// function to calculate number of
// factors
static int calculateNoOfFactors(int n)
{
if (n == 1)
return 1;
int ans = 1;
// stores the smallest prime
// number that divides n
int dup = factor[n];
// stores the count of number
// of times a prime number
// divides n.
int c = 1;
// reduces to the next number
// after prime factorization
// of n
int j = n / factor[n];
// false when prime factorization
// is done
while (j != 1) {
// if the same prime number
// is dividing n, then we
// increase the count
if (factor[j] == dup)
c += 1;
/* if its a new prime factor
that is factorizing n, then
we again set c=1 and change
dup to the new prime factor,
and apply the formula explained
above. */
else {
dup = factor[j];
ans = ans * (c + 1);
c = 1;
}
// prime factorizes a number
j = j / factor[j];
}
// for the last prime factor
ans = ans * (c + 1);
return ans;
}
/* Driver program to test above
function */
public static void Main()
{
// array to store prime factors
factor = new int[MAX];
factor[0] = 0;
// generate prime factors of number
// upto 10^6
generatePrimeFactors();
int[] a = { 10, 30, 100, 450, 987 };
int q = a.Length;
for (int i = 0; i < q; i++)
Console.Write(
calculateNoOFactors(a[i])
+ " ");
}
}
// This code is contributed by vt_m.
PHP
<?php
// It works properly on
// 64-bit PHP Compiler
// PHP program to count
// number of factors
// of an array of integers
$MAX = 1000001;
// array to store
// prime factors
$factor = array_fill(0, $MAX + 1, 0);
// function to generate all
// prime factors of numbers
// from 1 to 10^6
function generatePrimeFactors()
{
global $factor;
global $MAX;
$factor[1] = 1;
// Initializes all the
// positions with their value.
for ($i = 2; $i < $MAX; $i++)
$factor[$i] = $i;
// Initializes all
// multiples of 2 with 2
for ($i = 4; $i < $MAX; $i += 2)
$factor[$i] = 2;
// A modified version of
// Sieve of Eratosthenes
// to store the smallest
// prime factor that divides
// every number.
for ($i = 3; $i * $i < $MAX; $i++)
{
// check if it has
// no prime factor.
if ($factor[$i] == $i)
{
// Initializes of j
// starting from i*i
for ($j = $i * $i;
$j < $MAX; $j += $i)
{
// if it has no prime factor
// before, then stores the
// smallest prime divisor
if ($factor[$j] == $j)
$factor[$j] = $i;
}
}
}
}
// function to calculate
// number of factors
function calculateNoOfFactors($n)
{
global $factor;
if ($n == 1)
return 1;
$ans = 1;
// stores the smallest
// prime number that
// divides n
$dup = $factor[$n];
// stores the count of
// number of times a
// prime number divides n.
$c = 1;
// reduces to the next
// number after prime
// factorization of n
$j = (int)($n / $factor[$n]);
// false when prime
// factorization is done
while ($j != 1)
{
// if the same prime
// number is dividing
// n, then we increase
// the count
if ($factor[$j] == $dup)
$c += 1;
/* if its a new prime factor
that is factorizing n,
then we again set c=1 and
change dup to the new prime
factor, and apply the formula
explained above. */
else
{
$dup = $factor[$j];
$ans = $ans * ($c + 1);
$c = 1;
}
// prime factorizes
// a number
$j = (int)($j / $factor[$j]);
}
// for the last
// prime factor
$ans = $ans * ($c + 1);
return $ans;
}
// Driver Code
// generate prime factors
// of number upto 10^6
generatePrimeFactors();
$a = array(10, 30, 100, 450, 987);
$q = sizeof($a);
for ($i = 0; $i < $q; $i++)
echo calculateNoOFactors($a[$i]) . " ";
// This code is contributed
// by mits.
?>
Javascript
<script>
// javascript Code For Efficient program to print
// the number of factors of n numbers
var MAX = 1000001;
var factor = [];
// function to generate all prime
// factors of numbers from 1 to 10^6
function generatePrimeFactors() {
factor[1] = 1;
// Initializes all the positions with
// their value.
for (i = 2; i < MAX; i++)
factor[i] = i;
// Initializes all multiples of 2 with 2
for (i = 4; i < MAX; i += 2)
factor[i] = 2;
// A modified version of Sieve of
// Eratosthenes to store the
// smallest prime factor that
// divides every number.
for (i = 3; i * i < MAX; i++)
{
// check if it has no prime factor.
if (factor[i] == i)
{
// Initializes of j starting from i*i
for (j = i * i; j < MAX; j += i)
{
// if it has no prime factor
// before, then stores the
// smallest prime divisor
if (factor[j] == j)
factor[j] = i;
}
}
}
}
// function to calculate number of factors
function calculateNoOfFactors(n)
{
if (n == 1)
return 1;
var ans = 1;
// stores the smallest prime number
// that divides n
var dup = factor[n];
// stores the count of number of times
// a prime number divides n.
var c = 1;
// reduces to the next number after prime
// factorization of n
var j = n / factor[n];
// false when prime factorization is done
while (j != 1)
{
// if the same prime number is dividing n,
// then we increase the count
if (factor[j] == dup)
c += 1;
/*
* if its a new prime factor that is factorizing n, then we again set c=1 and
* change dup to the new prime factor, and apply the formula explained above.
*/
else
{
dup = factor[j];
ans = ans * (c + 1);
c = 1;
}
// prime factorizes a number
j = j / factor[j];
}
// for the last prime factor
ans = ans * (c + 1);
return ans;
}
/* Driver program to test above function */
// array to store prime factors
factor = Array(MAX).fill(0);
factor[0] = 0;
// generate prime factors of number
// upto 10^6
generatePrimeFactors();
var a = [ 10, 30, 100, 450, 987 ];
var q = a.length;
for (i = 0; i < q; i++)
document.write(calculateNoOFactors(a[i]) + " ");
// This code is contributed by aashish1995
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA