Dado un entero positivo n, encuentre el conteo de todos los múltiplos de 3 o 7 menores o iguales que n.
Ejemplos:
Input : n = 10 Output : Count = 4 The multiples are 3, 6, 7 and 9 Input : n = 25 Output : Count = 10 The multiples are 3, 6, 7, 9, 12, 14, 15, 18, 21 and 24
Una solución simple es iterar sobre todos los números del 1 al n e incrementar el conteo siempre que un número sea un múltiplo de 3 o 7 o ambos.
C++
// A Simple C++ program to find count of all
// numbers that multiples
#include<iostream>
using namespace std;
// Returns count of all numbers smaller than
// or equal to n and multiples of 3 or 7 or both
int countMultiples(int n)
{
int res = 0;
for (int i=1; i<=n; i++)
if (i%3==0 || i%7 == 0)
res++;
return res;
}
// Driver code
int main()
{
cout << "Count = " << countMultiples(25);
}
Java
// A Simple Java program to
// find count of all numbers
// that multiples
import java.io.*;
class GFG
{
// Returns count of all numbers
// smaller than or equal to n
// and multiples of 3 or 7 or both
static int countMultiples(int n)
{
int res = 0;
for (int i = 1; i <= n; i++)
if (i % 3 == 0 || i % 7 == 0)
res++;
return res;
}
// Driver Code
public static void main (String[] args)
{
System.out.print("Count = ");
System.out.println(countMultiples(25));
}
}
// This code is contributed by m_kit
Python3
# A Simple Python3 program to
# find count of all numbers
# that multiples
# Returns count of all numbers
# smaller than or equal to n
# and multiples of 3 or 7 or both
def countMultiples(n):
res = 0;
for i in range(1, n + 1):
if (i % 3 == 0 or i % 7 == 0):
res += 1;
return res;
# Driver code
print("Count =", countMultiples(25));
# This code is contributed by mits
C#
// A Simple C# program to
// find count of all numbers
// that are multiples of 3 or 7
using System;
class GFG
{
// Returns count of all
// numbers smaller than
// or equal to n and
// are multiples of 3 or
// 7 or both
static int countMultiples(int n)
{
int res = 0;
for (int i = 1; i <= n; i++)
if (i % 3 == 0 || i % 7 == 0)
res++;
return res;
}
// Driver Code
static public void Main ()
{
Console.Write("Count = ");
Console.WriteLine(countMultiples(25));
}
}
// This code is contributed by ajit
PHP
<?php
// A Simple PHP program to find count
// of all numbers that multiples
// Returns count of all numbers
// smaller than or equal to n
// and multiples of 3 or 7 or both
function countMultiples($n)
{
$res = 0;
for ($i = 1; $i <= $n; $i++)
if ($i % 3 == 0 || $i % 7 == 0)
$res++;
return $res;
}
// Driver code
echo "Count = " ,countMultiples(25);
// This code is contributed by aj_36
?>
Javascript
<script>
// A Simple JavaScript program to find count
// of all numbers that multiples
// Returns count of all numbers
// smaller than or equal to n
// and multiples of 3 or 7 or both
function countMultiples(n)
{
let res = 0;
for (let i = 1; i <= n; i++)
if (i % 3 == 0 || i % 7 == 0)
res++;
return res;
}
// Driver code
document.write( "Count = " +countMultiples(25));
// This code is contributed by bobby
</script>
Producción :
Count = 10
Complejidad del tiempo: O(n)
Una solución eficiente puede resolver el problema anterior en el tiempo O(1). La idea es contar múltiplos de 3 y sumar múltiplos de 7, luego restar múltiplos de 21 porque estos se cuentan dos veces.
count = n/3 + n/7 - n/21
C++
// A better C++ program to find count of all
// numbers that multiples
#include<iostream>
using namespace std;
// Returns count of all numbers smaller than
// or equal to n and multiples of 3 or 7 or both
int countMultiples(int n)
{
return n/3 + n/7 -n/21;
}
// Driver code
int main()
{
cout << "Count = " << countMultiples(25);
}
Java
// A better Java program to
// find count of all numbers
// that multiples
import java.io.*;
class GFG
{
// Returns count of all numbers
// smaller than or equal to n
// and multiples of 3 or 7 or both
static int countMultiples(int n)
{
return n / 3 + n / 7 - n / 21;
}
// Driver code
public static void main (String args [] )
{
System.out.println("Count = " +
countMultiples(25));
}
}
// This code is contributed by aj_36
Python 3
# Python 3 program to find count of
# all numbers that multiples
# Returns count of all numbers
# smaller than or equal to n and
# multiples of 3 or 7 or both
def countMultiples(n):
return n / 3 + n / 7 - n / 21;
# Driver code
n = ((int)(countMultiples(25)));
print("Count =", n);
# This code is contributed
# by Shivi_Aggarwal
C#
// A better Java program to
// find count of all numbers
// that multiples
using System;
class GFG
{
// Returns count of all numbers
// smaller than or equal to n
// and multiples of 3 or 7 or both
static int countMultiples(int n)
{
return n / 3 + n / 7 - n / 21;
}
// Driver Code
static public void Main ()
{
Console.WriteLine("Count = " +
countMultiples(25));
}
}
// This code is contributed by m_kit
PHP
<?php
// A better PHP program to find count
// of all numbers that multiples
// Returns count of all numbers
// smaller than or equal to n
// and multiples of 3 or 7 or both
function countMultiples($n)
{
return floor($n / 3 + $n / 7 - $n / 21);
}
// Driver code
echo "Count = " , countMultiples(25);
// This code is contributed by ajit
?>
Javascript
<script>
// JavaScript program to find count
// of all numbers that multiples
// Returns count of all numbers
// smaller than or equal to n
// and multiples of 3 or 7 or both
function countMultiples(n)
{
return Math.floor(n / 3 + n / 7 - n / 21);
}
// Driver code
document.write( "Count = " +countMultiples(25));
// This code is contributed by bobby
</script>
Producción :
Count = 10
Complejidad de tiempo: O(1)
Ejercicio:
Ahora intenta resolver el problema de encontrar la suma de todos los números menores o iguales que n y múltiplos de 3 o 7 o ambos en O(1) tiempo.
Este artículo es una contribución de Saurabh Gupta . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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