Cuente todos los números en un rango con el factor más pequeño como K

Posted on by Rudeus Greyrat

Dado un rango de enteros de ‘a’ a ‘b’ . Nuestra tarea es calcular la cantidad de números del intervalo [ a, b ] , que no son divisibles por ningún número entre 2 y k – 1 y, sin embargo, son divisibles por k . 
Nota: No tenemos que considerar un divisor igual a uno.
Ejemplos: 
 

Input : a = 12, b = 23, k = 3
Output : 2
Between [12, 23], 15 and 21 are the only number 
which are divisible k and not divisible by any 
number between 2 and k - 1.

Input : a = 1, b = 80, k = 7
Output : 3

Enfoque: a continuación se muestra el algoritmo paso a paso para resolver este problema:
 

  1. Un número es divisible solo por k y no por cualquier número menor que k solo si k es un número primo.
  2. Recorre cada número de a a b para comprobar si el número tiene el factor más pequeño como número primo k .
  3. Cuente todos esos números en el rango cuyo factor más pequeño es un número primo k .

A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ program to find the count of numbers in a range
// whose smallest factor is K
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if k is a prime number or not
bool isPrime(int k)
{
    // Corner case
    if (k <= 1)
        return false;
 
    // Check from 2 to n-1
    for (int i = 2; i < k; i++)
        if (k % i == 0)
            return false;
 
    return true;
}
 
// Function to check if a number is not divisible
// by any number between 2 and K-1
int check(int num, int k)
{
    int flag = 1;
 
    // to check if the num is divisible by
    // any numbers between 2 and k - 1
    for (int i = 2; i < k; i++) {
        if (num % i == 0)
            flag = 0;
    }
 
    if (flag == 1) {
        // if not divisible by any number between
        // 2 and k - 1
        // but divisible by k
        if (num % k == 0)
            return 1;
        else
            return 0;
    }
    else
        return 0;
}
 
// Function to find count of numbers in range [a, b]
// with smallest factor as K
int findCount(int a, int b, int k)
{
    int count = 0;
 
    // a number can be divisible only by k and
    // not by any number less than k only
    // if k is a prime
    if (!isPrime(k))
        return 0;
    else {
        int ans;
        for (int i = a; i <= b; i++) {
 
            // to check if a number has
            // smallest factor as K
            ans = check(i, k);
            if (ans == 1)
                count++;
            else
                continue;
        }
    }
 
    return count;
}
 
// Driver code
int main()
{
    int a = 2020, b = 6300, k = 29;
 
    cout << findCount(a, b, k);
 
    return 0;
}

Java

// Java program to find the count of numbers in a range
// whose smallest factor is K
 
public class GFG {
     
    // Function to check if k is a prime number or not
    static boolean isPrime(int k)
    {
        // Corner case
        if (k <= 1)
            return false;
 
        // Check from 2 to n-1
        for (int i = 2; i < k; i++)
            if (k % i == 0)
                return false;
 
        return true;
    }
 
    // Function to check if a number is not divisible
    // by any number between 2 and K-1
    static int check(int num, int k)
    {
        int flag = 1;
 
        // to check if the num is divisible by
        // any numbers between 2 and k - 1
        for (int i = 2; i < k; i++) {
            if (num % i == 0)
                flag = 0;
        }
 
        if (flag == 1) {
            // if not divisible by any number between
            // 2 and k - 1
            // but divisible by k
            if (num % k == 0)
                return 1;
            else
                return 0;
        }
        else
            return 0;
    }
 
    // Function to find count of numbers in range [a, b]
    // with smallest factor as K
    static int findCount(int a, int b, int k)
    {
        int count = 0;
 
        // a number can be divisible only by k and
        // not by any number less than k only
        // if k is a prime
        if (!isPrime(k))
            return 0;
        else {
            int ans;
            for (int i = a; i <= b; i++) {
 
                // to check if a number has
                // smallest factor as K
                ans = check(i, k);
                if (ans == 1)
                    count++;
                else
                    continue;
            }
        }
 
        return count;
    }
 
 
// Driver code
public static void main(String args[])
    {
         int a = 2020, b = 6300, k = 29;
 
            System.out.println(findCount(a, b, k));
   
    }
    // This Code is contributed by ANKITRAI1
}

Python 3

# Python 3 program to find the count
# of numbers in a range whose smallest
# factor is K
 
# Function to check if k is
# a prime number or not
def isPrime( k):
 
    # Corner case
    if (k <= 1):
        return False
 
    # Check from 2 to n-1
    for i in range(2, k):
        if (k % i == 0):
            return false
 
    return True
 
# Function to check if a number
# is not divisible by any number
# between 2 and K-1
def check(num, k):
    flag = 1
 
    # to check if the num is divisible
    # by any numbers between 2 and k - 1
    for i in range(2, k) :
        if (num % i == 0):
            flag = 0
 
    if (flag == 1) :
         
        # if not divisible by any
        # number between 2 and k - 1
        # but divisible by k
        if (num % k == 0):
            return 1
        else:
            return 0
    else:
        return 0
 
# Function to find count of
# numbers in range [a, b]
# with smallest factor as K
def findCount(a, b, k):
     
    count = 0
 
    # a number can be divisible only
    # by k and not by any number
    # less than k only if k is a prime
    if (not isPrime(k)):
        return 0
    else :
         
        for i in range(a, b + 1) :
 
            # to check if a number has
            # smallest factor as K
            ans = check(i, k)
            if (ans == 1):
                count += 1
            else:
                continue
 
    return count
 
# Driver code
if __name__ == "__main__":
    a = 2020
    b = 6300
    k = 29
 
    print(findCount(a, b, k))
 
# This code is contributed
# by ChitraNayal

C#

// C# program to find the count
// of numbers in a range whose
// smallest factor is K
using System;
 
class GFG
{
 
// Function to check if k is
// a prime number or not
static bool isPrime(int k)
{
    // Corner case
    if (k <= 1)
        return false;
 
    // Check from 2 to n-1
    for (int i = 2; i < k; i++)
        if (k % i == 0)
            return false;
 
    return true;
}
 
// Function to check if a number
// is not divisible by any number
// between 2 and K-1
static int check(int num, int k)
{
    int flag = 1;
 
    // to check if the num is divisible by
    // any numbers between 2 and k - 1
    for (int i = 2; i < k; i++)
    {
        if (num % i == 0)
            flag = 0;
    }
 
    if (flag == 1)
    {
        // if not divisible by any
        // number between 2 and k - 1
        // but divisible by k
        if (num % k == 0)
            return 1;
        else
            return 0;
    }
    else
        return 0;
}
 
// Function to find count of
// numbers in range [a, b]
// with smallest factor as K
static int findCount(int a, int b, int k)
{
    int count = 0;
 
    // a number can be divisible only
    // by k and not by any number less
    // than k only if k is a prime
    if (!isPrime(k))
        return 0;
    else
    {
        int ans;
        for (int i = a; i <= b; i++)
        {
 
            // to check if a number has
            // smallest factor as K
            ans = check(i, k);
            if (ans == 1)
                count++;
            else
                continue;
        }
    }
 
    return count;
}
 
// Driver code
public static void Main()
{
    int a = 2020, b = 6300, k = 29;
 
    Console.WriteLine(findCount(a, b, k));
}
}
 
// This code is contributed
// by Akanksha Rai(Abby_akku)

PHP

<?php
// PHP program to find the count
// of numbers in a range whose
// smallest factor is K
 
// Function to check if k is
// a prime number or not
function isPrime($k)
{
    // Corner case
    if ($k <= 1)
        return false;
 
    // Check from 2 to n-1
    for ($i = 2; $i < $k; $i++)
        if ($k % $i == 0)
            return false;
 
    return true;
}
 
// Function to check if a number
// is not divisible by any number
// between 2 and K-1
function check($num, $k)
{
    $flag = 1;
 
    // to check if the num is divisible
    // by any numbers between 2 and k - 1
    for ($i = 2; $i < $k; $i++)
    {
        if ($num % $i == 0)
            $flag = 0;
    }
 
    if ($flag == 1)
    {
        // if not divisible by any
        // number between 2 and k - 1
        // but divisible by k
        if ($num % $k == 0)
            return 1;
        else
            return 0;
    }
    else
        return 0;
}
 
// Function to find count of
// numbers in range [a, b]
// with smallest factor as K
function findCount($a, $b, $k)
{
    $count = 0;
 
    // a number can be divisible
    // only by k and not by any
    // number less than k only
    // if k is a prime
    if (!isPrime($k))
        return 0;
    else
    {
        for ($i = $a; $i <= $b; $i++)
        {
 
            // to check if a number has
            // smallest factor as K
            $ans = check($i, $k);
            if ($ans == 1)
                $count++;
            else
                continue;
        }
    }
 
    return $count;
}
 
// Driver code
$a = 2020;
$b = 6300;
$k = 29;
 
echo (findCount($a, $b, $k));
 
// This code is contributed
// by Shivi_Aggarwal
?>

Javascript

<script>
// Javascript program to find the count of numbers in a range
// whose smallest factor is K
     
    // Function to check if k is a prime number or not
    function isPrime(k)
    {
        // Corner case
        if (k <= 1)
            return false;
   
        // Check from 2 to n-1
        for (let i = 2; i < k; i++)
            if (k % i == 0)
                return false;
   
        return true;
    }
     
    // Function to check if a number is not divisible
    // by any number between 2 and K-1
    function check(num,k)
    {
        let flag = 1;
   
        // to check if the num is divisible by
        // any numbers between 2 and k - 1
        for (let i = 2; i < k; i++) {
            if (num % i == 0)
                flag = 0;
        }
   
        if (flag == 1) {
            // if not divisible by any number between
            // 2 and k - 1
            // but divisible by k
            if (num % k == 0)
                return 1;
            else
                return 0;
        }
        else
            return 0;
    }
     
    // Function to find count of numbers in range [a, b]
    // with smallest factor as K
    function findCount(a,b,k)
    {
        let count = 0;
   
        // a number can be divisible only by k and
        // not by any number less than k only
        // if k is a prime
        if (!isPrime(k))
            return 0;
        else {
            let ans;
            for (let i = a; i <= b; i++) {
   
                // to check if a number has
                // smallest factor as K
                ans = check(i, k);
                if (ans == 1)
                    count++;
                else
                    continue;
            }
        }
   
        return count;
    }
     
    // Driver code
    let a = 2020, b = 6300, k = 29;
    document.write(findCount(a, b, k));
     
 
// This code is contributed by avanitrachhadiya2155
</script>
Producción: 

28

 

Complejidad temporal: O(ba)*k
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por SrijaDe y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *