Dados dos números positivos A y B . La tarea es imprimir todos los
Número panarítmico entre dos números (inclusive).
Los números panarítmicos o números prácticos son un número entero positivo N tal que todos los números enteros positivos menores que N pueden representarse como sumas de distintos divisores de N .
Por ejemplo: , 12 es un número práctico porque todos los números del 1 al 11 se pueden expresar como sumas de sus divisores 1, 2, 3, 4 y 6 { 5 = 3 + 2, 7 = 6 + 1, 8 = 6 + 2, 9 = 6 + 3, 10 = 6 + 3 + 1, 11 = 6 + 3 + 2}
Ejemplos:
Entrada: A = 1 B = 20
Salida: 1 2 4 6 8 12 16 18 20
Explicación:
Hay 9 números prácticos y estos son los números cuyos factores pueden representar todo el número menor que él.
Por ejemplo, 4. Los factores de 4 son 1 y 2.
El número 3 se puede representar como 1+2 = 3.Entrada: A = 100 B = 150
Salida: 100 104 108 112 120 126 128 132 140 144 150
Acercarse:
- Iterar de A a B (inclusive).
- Compruebe para cada número si es un número práctico o no.
- Calcule y almacene los factores de cada número dentro de [A, B] uno por uno y verifique si todos los números menores que los números respectivos se pueden expresar como la suma de los factores.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to print Practical
// Numbers in given range
#include <bits/stdc++.h>
using namespace std;
// function to compute divisors
// of a number
vector<int> get_divisors(int A)
{
// vector to store divisors
vector<int> ans;
// 1 will always be a divisor
ans.push_back(1);
for (int i = 2; i <= sqrt(A); i++) {
if (A % i == 0) {
ans.push_back(i);
// check if i is squareroot
// of A then only one time
// insert it in ans
if ((i * i) != A)
ans.push_back(A / i);
}
}
return ans;
}
// function to check that a
// number can be represented as
// sum of distinct divisor or not
bool Sum_Possible(vector<int> set, int sum)
{
int n = set.size();
// The value of subset[i][j]
// will be true if
// there is a subset of
// set[0..j-1] with sum
// equal to i
bool subset[n + 1][sum + 1];
// If sum is 0, then answer is true
for (int i = 0; i <= n; i++)
subset[i][0] = true;
// If sum is not 0 and set is empty,
// then answer is false
for (int i = 1; i <= sum; i++)
subset[0][i] = false;
// Fill the subset table
// in bottom up manner
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= sum; j++) {
if (j < set[i - 1])
subset[i][j] = subset[i - 1][j];
if (j >= set[i - 1])
subset[i][j]
= subset[i - 1][j]
|| subset[i - 1]
[j - set[i - 1]];
}
}
// return the possibility
// of given sum
return subset[n][sum];
}
// function to check a number is
// Practical or not
bool Is_Practical(int A)
{
// vector to store divisors
vector<int> divisors;
divisors = get_divisors(A);
for (int i = 2; i < A; i++) {
if (Sum_Possible(divisors, i) == false)
return false;
}
// if all numbers can be
// represented as sum of
// unique divisors
return true;
}
// function to print Practical
// Numbers in a range
void print_practica_No(int A, int B)
{
for (int i = A; i <= B; i++) {
if (Is_Practical(i) == true) {
cout << i << " ";
}
}
}
// Driver Function
int main()
{
int A = 1, B = 100;
print_practica_No(A, B);
return 0;
}
Java
// Java program to print practical
// Numbers in given range
import java.util.*;
import java.math.*;
class GFG{
// Function to compute divisors
// of a number
static ArrayList<Integer> get_divisors(int A)
{
// Vector to store divisors
ArrayList<Integer> ans = new ArrayList<>();
// 1 will always be a divisor
ans.add(1);
for(int i = 2; i <= Math.sqrt(A); i++)
{
if (A % i == 0)
{
ans.add(i);
// Check if i is squareroot
// of A then only one time
// insert it in ans
if ((i * i) != A)
ans.add(A / i);
}
}
return ans;
}
// Function to check that a
// number can be represented as
// sum of distinct divisor or not
static boolean Sum_Possible(ArrayList<Integer> set,
int sum)
{
int n = set.size();
// The value of subset[i][j]
// will be true if there is
// a subset of set[0..j-1]
// with sum equal to i
boolean subset[][] = new boolean[n + 1][sum + 1];
// If sum is 0, then answer is true
for(int i = 0; i <= n; i++)
subset[i][0] = true;
// If sum is not 0 and set is empty,
// then answer is false
for(int i = 1; i <= sum; i++)
subset[0][i] = false;
// Fill the subset table
// in bottom up manner
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= sum; j++)
{
if (j < set.get(i - 1))
subset[i][j] = subset[i - 1][j];
if (j >= set.get(i - 1))
subset[i][j] = subset[i - 1][j] ||
subset[i - 1][j -
set.get(i - 1)];
}
}
// Return the possibility
// of given sum
return subset[n][sum];
}
// Function to check a number is
// Practical or not
static boolean Is_Practical(int A)
{
// Vector to store divisors
ArrayList<Integer> divisors;
divisors = get_divisors(A);
for(int i = 2; i < A; i++)
{
if (Sum_Possible(divisors, i) == false)
return false;
}
// If all numbers can be
// represented as sum of
// unique divisors
return true;
}
// Function to print Practical
// Numbers in a range
static void print_practica_No(int A, int B)
{
for(int i = A; i <= B; i++)
{
if (Is_Practical(i) == true)
{
System.out.print(i + " ");
}
}
}
// Driver Code
public static void main(String args[])
{
int A = 1, B = 100;
print_practica_No(A, B);
}
}
// This code is contributed by jyoti369
Python3
# Python3 program to print Practical # Numbers in given range import math # Function to compute divisors # of a number def get_divisors(A): # Vector to store divisors ans = [] # 1 will always be a divisor ans.append(1) for i in range(2, math.floor(math.sqrt(A)) + 1): if (A % i == 0): ans.append(i) # Check if i is squareroot # of A then only one time # insert it in ans if ((i * i) != A): ans.append(A // i) return ans # Function to check that a # number can be represented as # summ of distinct divisor or not def summ_Possible(sett, summ): n = len(sett) # The value of subsett[i][j] will # be True if there is a subsett of # sett[0..j-1] with summ equal to i subsett = [[0 for i in range(summ + 1)] for j in range(n + 1)] # If summ is 0, then answer is True for i in range(n + 1): subsett[i][0] = True # If summ is not 0 and sett is empty, # then answer is False for i in range(1, summ + 1): subsett[0][i] = False # Fill the subsett table # in bottom up manner for i in range(n + 1): for j in range(summ + 1): if (j < sett[i - 1]): subsett[i][j] = subsett[i - 1][j] if (j >= sett[i - 1]): subsett[i][j] = (subsett[i - 1][j] or subsett[i - 1] [j - sett[i - 1]]) # Return the possibility # of given summ return subsett[n][summ] # Function to check a number # is Practical or not def Is_Practical(A): # Vector to store divisors divisors = [] divisors = get_divisors(A) for i in range(2, A): if (summ_Possible(divisors, i) == False): return False # If all numbers can be # represented as summ of # unique divisors return True # Function to prPractical # Numbers in a range def print_practica_No(A, B): for i in range(A, B + 1): if (Is_Practical(i) == True): print(i, end = " ") # Driver code A = 1 B = 100 print_practica_No(A, B) # This code is contributed by shubhamsingh10
C#
// C# program to print practical
// Numbers in given range
using System;
using System.Collections;
class GFG{
// Function to compute divisors
// of a number
static ArrayList get_divisors(int A)
{
// To store divisors
ArrayList ans = new ArrayList();
// 1 will always be a divisor
ans.Add(1);
for(int i = 2;
i <= (int)Math.Sqrt(A);
i++)
{
if (A % i == 0)
{
ans.Add(i);
// Check if i is squareroot
// of A then only one time
// insert it in ans
if ((i * i) != A)
ans.Add(A / i);
}
}
return ans;
}
// Function to check that a
// number can be represented as
// sum of distinct divisor or not
static bool Sum_Possible(ArrayList set,
int sum)
{
int n = set.Count;
// The value of subset[i][j]
// will be true if
// there is a subset of
// set[0..j-1] with sum
// equal to i
bool [,]subset = new bool[n + 1, sum + 1];
// If sum is 0, then answer is true
for(int i = 0; i <= n; i++)
subset[i, 0] = true;
// If sum is not 0 and set is empty,
// then answer is false
for(int i = 1; i <= sum; i++)
subset[0, i] = false;
// Fill the subset table
// in bottom up manner
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= sum; j++)
{
if (j < (int)set[i - 1])
subset[i, j] = subset[i - 1, j];
if (j >= (int)set[i - 1])
subset[i, j] = subset[i - 1, j] ||
subset[i - 1, j -
(int)set[i - 1]];
}
}
// Return the possibility
// of given sum
return subset[n, sum];
}
// Function to check a number is
// Practical or not
static bool Is_Practical(int A)
{
// To store divisors
ArrayList divisors = new ArrayList();
divisors = get_divisors(A);
for(int i = 2; i < A; i++)
{
if (Sum_Possible(divisors, i) == false)
return false;
}
// If all numbers can be
// represented as sum of
// unique divisors
return true;
}
// Function to print Practical
// Numbers in a range
static void print_practica_No(int A, int B)
{
for(int i = A; i <= B; i++)
{
if (Is_Practical(i) == true)
{
Console.Write(i + " ");
}
}
}
// Driver code
public static void Main(string []args)
{
int A = 1, B = 100;
print_practica_No(A, B);
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript program to print Practical
// Numbers in given range
// function to compute divisors
// of a number
function get_divisors(A)
{
// vector to store divisors
var ans = [];
// 1 will always be a divisor
ans.push(1);
for (var i = 2; i <= Math.sqrt(A); i++) {
if (A % i == 0) {
ans.push(i);
// check if i is squareroot
// of A then only one time
// insert it in ans
if ((i * i) != A)
ans.push(parseInt(A / i));
}
}
return ans;
}
// function to check that a
// number can be represented as
// sum of distinct divisor or not
function Sum_Possible(set, sum)
{
var n = set.length;
// The value of subset[i][j]
// will be true if
// there is a subset of
// set[0..j-1] with sum
// equal to i
var subset = Array.from(Array(n+1), ()=>Array(sum+1));
// If sum is 0, then answer is true
for (var i = 0; i <= n; i++)
subset[i][0] = true;
// If sum is not 0 and set is empty,
// then answer is false
for (var i = 1; i <= sum; i++)
subset[0][i] = false;
// Fill the subset table
// in bottom up manner
for (var i = 1; i <= n; i++) {
for (var j = 1; j <= sum; j++) {
if (j < set[i - 1])
subset[i][j] = subset[i - 1][j];
if (j >= set[i - 1])
subset[i][j]
= subset[i - 1][j]
|| subset[i - 1]
[j - set[i - 1]];
}
}
// return the possibility
// of given sum
return subset[n][sum];
}
// function to check a number is
// Practical or not
function Is_Practical(A)
{
// vector to store divisors
var divisors = [];
divisors = get_divisors(A);
for (var i = 2; i < A; i++) {
if (Sum_Possible(divisors, i) == false)
return false;
}
// if all numbers can be
// represented as sum of
// unique divisors
return true;
}
// function to print Practical
// Numbers in a range
function print_practica_No(A, B)
{
for (var i = A; i <= B; i++) {
if (Is_Practical(i) == true) {
document.write( i + " ");
}
}
}
// Driver Function
var A = 1, B = 100;
print_practica_No(A, B);
// This code is contributed by noob2000.
</script>
Producción:
1 2 4 6 8 12 16 18 20 24 28 30 32 36 40 42 48 54 56 60 64 66 72 78 80 84 88 90 96 100
Complejidad de Tiempo: O(( B – A) * B 5/2 )
Espacio Auxiliar: O( B 3/2 )
Publicación traducida automáticamente
Artículo escrito por thakurabhaysingh445 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA