Кратно 3 или 7

31.12.2019Математика

Учитывая положительное целое число n, найдите число всех кратных 3 или 7, меньших или равных n.

Примеры :

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

Простое решение состоит в том, чтобы перебирать все числа от 1 до n и увеличивать счетчик всякий раз, когда число кратно 3 или 7 или обоим.

C ++

// Простая программа на C ++ для поиска количества всех
// числа, которые умножаются
#include<iostream>

using namespace std;

// Возвращает количество всех чисел меньше
// или равно n и кратно 3 или 7 или обоим

int countMultiples(int n)

{

int res = 0;

for (int i=1; i<=n; i++)

if (i%3==0 || i%7 == 0)

res++;

return res;

}

// Код драйвера

int main()

{

cout << "Count = " << countMultiples(25);

}

Джава

// Простая Java-программа для
// найти количество всех чисел
// это кратно

import java.io.*;

class GFG

{

// Возвращает количество всех чисел
// меньше или равно n
// и множество из 3 или 7 или оба

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;

}

// Код драйвера

public static void main (String[] args)

{

System.out.print("Count = ");

System.out.println(countMultiples(25));

}
}

// Этот код предоставлен m_kit

python3

# Простая программа на Python3 для
# найти количество всех чисел
#, который умножается

# Возвращает количество всех чисел
# меньше или равно n
# и множество 3 или 7 или оба

def countMultiples(n):

res = 0;

for i in range(1, n + 1):

if (i % 3 == 0 or i % 7 == 0):

res += 1;

return res;

# Код драйвера

print("Count =", countMultiples(25));

# Этот код предоставлен mits

C #

// Простая программа на C # для
// найти количество всех чисел
// которые кратны 3 или 7

using System;

class GFG

{

// Возвращает количество всех
// числа меньше чем
// или равно n и
// кратны 3 или
// 7 или оба

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;

}

// Код драйвера

static public void Main ()

{

Console.Write("Count = ");

Console.WriteLine(countMultiples(25));

}
}

// Этот код предоставлен ajit

PHP

<?php
// Простая PHP-программа для поиска количества
// всех чисел, которые умножаются

// Возвращает количество всех чисел
// меньше или равно n
// и множество из 3 или 7 или оба

function countMultiples($n)

{

$res = 0;

for ($i = 1; $i <= $n; $i++)

if ($i % 3 == 0 || $i % 7 == 0)

$res++;

return $res;

}

// Код драйвера

echo "Count = " ,countMultiples(25);

// Этот код предоставлен aj_36
?>

Выход :

Count = 10

Сложность времени: O (n)

Эффективное решение может решить вышеуказанную проблему за O (1) раз. Идея состоит в том, чтобы посчитать кратные 3 и сложить кратные 7, а затем вычесть кратные 21, потому что они учитываются дважды.

count = n/3 + n/7 - n/21

C ++

// Лучшая программа на C ++ для подсчета всех
// числа, которые умножаются
#include<iostream>

using namespace std;

// Возвращает количество всех чисел меньше
// или равно n и кратно 3 или 7 или обоим

int countMultiples(int n)

{

return n/3 + n/7 -n/21;

}

// Код драйвера

int main()

{

cout << "Count = " << countMultiples(25);

}

Джава

// Лучшая Java-программа для
// найти количество всех чисел
// это кратно

import java.io.*;

class GFG

{

// Возвращает количество всех чисел
// меньше или равно n
// и множество из 3 или 7 или оба

static int countMultiples(int n)

{

return n / 3 + n / 7 - n / 21;

}

// Код драйвера

public static void main (String args [] )

{

System.out.println("Count = " +

countMultiples(25));

}
}

// Этот код предоставлен aj_36

Python 3

# Python 3 программа для поиска количества
# все числа, которые умножаются

# Возвращает количество всех чисел
# меньше или равно n и
# множество из 3 или 7 или обоих

def countMultiples(n):

return n / 3 + n / 7 - n / 21;

# Код драйвера

n = ((int)(countMultiples(25)));

print("Count =", n);

# Этот код добавлен
# by Shivi_Aggarwal

C #

// Лучшая Java-программа для
// найти количество всех чисел
// это кратно

using System;

class GFG

{

// Возвращает количество всех чисел
// меньше или равно n
// и множество из 3 или 7 или оба

static int countMultiples(int n)

{

return n / 3 + n / 7 - n / 21;

}

// Код драйвера

static public void Main ()

{

Console.WriteLine("Count = " +

countMultiples(25));

}
}

// Этот код предоставлен m_kit

PHP

<?php
// Лучшая PHP-программа для подсчета
// всех чисел, которые умножаются

// Возвращает количество всех чисел
// меньше или равно n
// и множество из 3 или 7 или оба

function countMultiples($n)

{

return floor($n / 3 + $n / 7 - $n / 21);

}

// Код драйвера

echo "Count = " , countMultiples(25);

// Этот код предоставлен ajit
?>

Выход :

Count = 10

Сложность времени: O (1)

Упражнение:
Теперь попробуйте найти сумму всех чисел, меньших или равных n и кратных 3, 7 или обоим за O (1).

Эта статья предоставлена Саурабх Гуптой . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Кратно 3 или 7

0.00 (0%) 0 votes