Dado un entero positivo N , la tarea es encontrar la diferencia absoluta del conteo de factores pares e impares de N .
Ejemplos:
Entrada: N = 12
Salida: 2
Explicación: Los factores pares de 12 son {2, 4, 6, 12}. Por lo tanto, la cuenta es 4.
Los factores impares de 12 son {1, 3}. Por lo tanto, el conteo es 2.
Por lo tanto, la diferencia entre sus conteos es (4 – 2) = 2.Entrada: N = 9
Salida: 3
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es encontrar todos los divisores del número N y luego encontrar la diferencia absoluta del conteo de los divisores pares e impares de N.
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar y se basa en las siguientes observaciones:
- De acuerdo con el teorema de factorización única , cualquier número puede expresarse en términos del producto de la potencia de los números primos. Por lo tanto, N se puede expresar como:
N = P 1 A 1 * P 2 A 2 * P 3 A 3 * ……… * P k A K
donde, cada P i es un número primo y cada A i es un número entero positivo.(1 ≤ i ≤ K)
- Por lo tanto, el número total de factores = (A 1 + 1)*(A 2 + 1)*(A 3 + 1)* ……… *(A 4 + 1) . Sea esta cuenta T .
- El número total de factores impares se puede calcular excluyendo la potencia de 2 en la fórmula anterior. Sea esta cuenta O .
- El número total de factores pares es igual a la diferencia entre el número total de factores y el número total de factores impares.
Por lo tanto, la idea es encontrar los factores primos y sus potencias en la descomposición en factores primos de N utilizando la criba de Eratóstenes e imprimir el valor absoluto de la diferencia del número total de factores y el doble del número total de factores impares como el resultado, es decir, abs(T – 2*O) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the smallest prime
// factor of all the numbers using
// Sieve Of Eratosthenes
void sieveOfEratosthenes(int N, int s[])
{
// Stores whether any number
// is prime or not
vector<bool> prime(N + 1, false);
// Initialize smallest factor as
// 2 for all the even numbers
for (int i = 2; i <= N; i += 2)
s[i] = 2;
// Iterate over the range [3, N]
for (int i = 3; i <= N; i += 2) {
// If i is prime
if (prime[i] == false) {
s[i] = i;
// Iterate all multiples of i
for (int j = i; j * i <= N;
j += 2) {
// i is the smallest
// prime factor of i * j
if (!prime[i * j]) {
prime[i * j] = true;
s[i * j] = i;
}
}
}
}
}
// Function to find the absolute
// difference between the count
// of odd and even factors of N
void findDifference(int N)
{
// Stores the smallest
// prime factor of i
int s[N + 1];
// Fill values in s[] using
// sieve of eratosthenes
sieveOfEratosthenes(N, s);
// Stores the total number of
// factors and the total number
// of odd and even factors
int total = 1, odd = 1, even = 0;
// Store the current prime
// factor of the number N
int curr = s[N];
// Store the power of
// current prime factor
int cnt = 1;
// Loop while N is greater than 1
while (N > 1) {
N /= s[N];
// If N also has smallest
// prime factor as curr, then
// increment cnt by 1
if (curr == s[N]) {
cnt++;
continue;
}
// Update only total number
// of factors if curr is 2
if (curr == 2) {
total = total * (cnt + 1);
}
// Update total number of
// factors and total number
// of odd factors
else {
total = total * (cnt + 1);
odd = odd * (cnt + 1);
}
// Update current prime
// factor as s[N] and
// count as 1
curr = s[N];
cnt = 1;
}
// Calculate the number
// of even factors
even = total - odd;
// Print the difference
cout << abs(even - odd);
}
// Driver Code
int main()
{
int N = 12;
findDifference(N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the smallest prime
// factor of all the numbers using
// Sieve Of Eratosthenes
static void sieveOfEratosthenes(int N, int s[])
{
// Stores whether any number
// is prime or not
boolean []prime = new boolean[N + 1];
// Initialize smallest factor as
// 2 for all the even numbers
for(int i = 2; i <= N; i += 2)
s[i] = 2;
// Iterate over the range [3, N]
for(int i = 3; i <= N; i += 2)
{
// If i is prime
if (prime[i] == false)
{
s[i] = i;
// Iterate all multiples of i
for(int j = i; j * i <= N; j += 2)
{
// i is the smallest
// prime factor of i * j
if (!prime[i * j])
{
prime[i * j] = true;
s[i * j] = i;
}
}
}
}
}
// Function to find the absolute
// difference between the count
// of odd and even factors of N
static void findDifference(int N)
{
// Stores the smallest
// prime factor of i
int []s = new int[N + 1];
// Fill values in s[] using
// sieve of eratosthenes
sieveOfEratosthenes(N, s);
// Stores the total number of
// factors and the total number
// of odd and even factors
int total = 1, odd = 1, even = 0;
// Store the current prime
// factor of the number N
int curr = s[N];
// Store the power of
// current prime factor
int cnt = 1;
// Loop while N is greater than 1
while (N > 1)
{
N /= s[N];
// If N also has smallest
// prime factor as curr, then
// increment cnt by 1
if (curr == s[N])
{
cnt++;
continue;
}
// Update only total number
// of factors if curr is 2
if (curr == 2)
{
total = total * (cnt + 1);
}
// Update total number of
// factors and total number
// of odd factors
else
{
total = total * (cnt + 1);
odd = odd * (cnt + 1);
}
// Update current prime
// factor as s[N] and
// count as 1
curr = s[N];
cnt = 1;
}
// Calculate the number
// of even factors
even = total - odd;
// Print the difference
System.out.print(Math.abs(even - odd));
}
// Driver Code
public static void main(String[] args)
{
int N = 12;
findDifference(N);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach # Function to find the smallest prime # factor of all the numbers using # Sieve Of Eratosthenes def sieveOfEratosthenes(N, s): # Stores whether any number # is prime or not prime = [False]*(N + 1) # Initialize smallest factor as # 2 for all the even numbers for i in range(2, N + 1, 2): s[i] = 2 # Iterate over the range [3, N] for i in range(3, N, 2): # If i is prime if (prime[i] == False): s[i] = i # Iterate all multiples of i for j in range(i, N, 2): if j * i > N: break # i is the smallest # prime factor of i * j if (not prime[i * j]): prime[i * j] = True s[i * j] = i # Function to find the absolute # difference between the count # of odd and even factors of N def findDifference(N): # Stores the smallest # prime factor of i s = [0]*(N+1) # Fill values in s[] using # sieve of eratosthenes sieveOfEratosthenes(N, s) # Stores the total number of # factors and the total number # of odd and even factors total , odd , even =1, 1, 0 # Store the current prime # factor of the number N curr = s[N] # Store the power of # current prime factor cnt = 1 # Loop while N is greater than 1 while (N > 1): N //= s[N] # If N also has smallest # prime factor as curr, then # increment cnt by 1 if (curr == s[N]): cnt += 1 continue # Update only total number # of factors if curr is 2 if (curr == 2): total = total * (cnt + 1) # Update total number of # factors and total number # of odd factors else: total = total * (cnt + 1) odd = odd * (cnt + 1) # Update current prime # factor as s[N] and # count as 1 curr = s[N] cnt = 1 # Calculate the number # of even factors even = total - odd # Print the difference print(abs(even - odd)) # Driver Code if __name__ == '__main__': N = 12 findDifference(N) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
class GFG
{
// Function to find the smallest prime
// factor of all the numbers using
// Sieve Of Eratosthenes
static void sieveOfEratosthenes(int N, int[] s)
{
// Stores whether any number
// is prime or not
bool[] prime = new bool[N + 1];
// Initialize smallest factor as
// 2 for all the even numbers
for (int i = 2; i <= N; i += 2)
s[i] = 2;
// Iterate over the range [3, N]
for (int i = 3; i <= N; i += 2) {
// If i is prime
if (prime[i] == false) {
s[i] = i;
// Iterate all multiples of i
for (int j = i; j * i <= N; j += 2) {
// i is the smallest
// prime factor of i * j
if (!prime[i * j]) {
prime[i * j] = true;
s[i * j] = i;
}
}
}
}
}
// Function to find the absolute
// difference between the count
// of odd and even factors of N
static void findDifference(int N)
{
// Stores the smallest
// prime factor of i
int[] s = new int[N + 1];
// Fill values in s[] using
// sieve of eratosthenes
sieveOfEratosthenes(N, s);
// Stores the total number of
// factors and the total number
// of odd and even factors
int total = 1, odd = 1, even = 0;
// Store the current prime
// factor of the number N
int curr = s[N];
// Store the power of
// current prime factor
int cnt = 1;
// Loop while N is greater than 1
while (N > 1) {
N /= s[N];
// If N also has smallest
// prime factor as curr, then
// increment cnt by 1
if (curr == s[N]) {
cnt++;
continue;
}
// Update only total number
// of factors if curr is 2
if (curr == 2) {
total = total * (cnt + 1);
}
// Update total number of
// factors and total number
// of odd factors
else {
total = total * (cnt + 1);
odd = odd * (cnt + 1);
}
// Update current prime
// factor as s[N] and
// count as 1
curr = s[N];
cnt = 1;
}
// Calculate the number
// of even factors
even = total - odd;
// Print the difference
Console.Write(Math.Abs(even - odd));
}
// Driver Code
public static void Main()
{
int N = 12;
findDifference(N);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// Javascript implementation of the above approach
// Function to find the smallest prime
// factor of all the numbers using
// Sieve Of Eratosthenes
function sieveOfEratosthenes(N, s)
{
// Stores whether any number
// is prime or not
let prime = Array.from({length: N+1}, (_, i) => 0);
// Initialize smallest factor as
// 2 for all the even numbers
for(let i = 2; i <= N; i += 2)
s[i] = 2;
// Iterate over the range [3, N]
for(let i = 3; i <= N; i += 2)
{
// If i is prime
if (prime[i] == false)
{
s[i] = i;
// Iterate all multiples of i
for(let j = i; j * i <= N; j += 2)
{
// i is the smallest
// prime factor of i * j
if (!prime[i * j])
{
prime[i * j] = true;
s[i * j] = i;
}
}
}
}
}
// Function to find the absolute
// difference between the count
// of odd and even factors of N
function findDifference(N)
{
// Stores the smallest
// prime factor of i
let s = Array.from({length: N+1}, (_, i) => 0);
// Fill values in s[] using
// sieve of eratosthenes
sieveOfEratosthenes(N, s);
// Stores the total number of
// factors and the total number
// of odd and even factors
let total = 1, odd = 1, even = 0;
// Store the current prime
// factor of the number N
let curr = s[N];
// Store the power of
// current prime factor
let cnt = 1;
// Loop while N is greater than 1
while (N > 1)
{
N /= s[N];
// If N also has smallest
// prime factor as curr, then
// increment cnt by 1
if (curr == s[N])
{
cnt++;
continue;
}
// Update only total number
// of factors if curr is 2
if (curr == 2)
{
total = total * (cnt + 1);
}
// Update total number of
// factors and total number
// of odd factors
else
{
total = total * (cnt + 1);
odd = odd * (cnt + 1);
}
// Update current prime
// factor as s[N] and
// count as 1
curr = s[N];
cnt = 1;
}
// Calculate the number
// of even factors
even = total - odd;
// Print the difference
document.write(Math.abs(even - odd));
}
// Driver Code
let N = 12;
findDifference(N);
</script>
Producción:
2
Complejidad de Tiempo: O(N*(log log N))
Espacio Auxiliar: O(N), ya que se ha tomado n espacio extra.