Given a range [L, R], the task is to find all the numbers from the range which are composite as well as the eventual sum of their digits is 1.
Examples:
Input: L = 10, R = 100
Output: 10 28 46 55 64 82 91 100
10 = 1 + 0 = 1
28 = 2 + 8 = 10 = 1 + 0 = 1
…
91 = 9 + 1 = 10 = 1 + 0 = 1
100 = 1 + 0 + 0 = 1
Input: L = 250, R = 350
Output: 253 262 280 289 298 316 325 334 343
Approach: For every number in the range check if the number is composite i.e. it has a divisor other than 1 and the number itself. If the current number is a composite number then keep on calculating the sum of its digits until the number is reduced to a single digit, if this digit is 1 then the chosen number is a valid number.
Below is the implementation of the above approach:
C++
#include <iostream>
using namespace std;
bool isComposite(int n)
{
if (n <= 1)
return false;
if (n <= 3)
return false;
if (n % 2 == 0 || n % 3 == 0)
return true;
for (int i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return true;
return false;
}
bool isDigitSumOne(int nm)
{
while (nm > 9) {
int sum_digit = 0;
while (nm > 0) {
int digit = nm % 10;
sum_digit = sum_digit + digit;
nm = nm / 10;
}
nm = sum_digit;
}
if (nm == 1)
return true;
else
return false;
}
void printValidNums(int l, int r)
{
for (int i = l; i <= r; i++) {
if (isComposite(i) && isDigitSumOne(i))
cout << i << " ";
}
}
int main(void)
{
int l = 10, r = 100;
printValidNums(l, r);
return 0;
}
Java
public class GFG {
static boolean isComposite(int n)
{
if (n <= 1)
return false;
if (n <= 3)
return false;
if (n % 2 == 0 || n % 3 == 0)
return true;
for (int i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return true;
return false;
}
static boolean isDigitSumOne(int nm)
{
while (nm > 9) {
int sum_digit = 0;
while (nm > 0) {
int digit = nm % 10;
sum_digit = sum_digit + digit;
nm = nm / 10;
}
nm = sum_digit;
}
if (nm == 1)
return true;
else
return false;
}
static void printValidNums(int l, int r)
{
for (int i = l; i <= r; i++) {
if (isComposite(i) && isDigitSumOne(i))
System.out.print(i + " ");
}
}
public static void main(String arg[])
{
int l = 10, r = 100;
printValidNums(l, r);
}
}
Python3
def isComposite(n):
if (n <= 1):
return False
if (n <= 3):
return False
if (n % 2 == 0 or n % 3 == 0):
return True
i = 5
while(i * i <= n):
if (n % i == 0 or n % (i + 2) == 0):
return True
i = i + 6
return False
def isDigitSumOne(nm) :
while(nm>9) :
sum_digit = 0
while(nm != 0) :
digit = nm % 10
sum_digit = sum_digit + digit
nm = nm // 10
nm = sum_digit
if(nm == 1):
return True
else:
return False
def printValidNums(m, n ):
for i in range(m, n + 1):
if(isComposite(i) and isDigitSumOne(i)) :
print(i, end =" ")
l = 10
r = 100
printValidNums(m, n)
C#
using System;
class GFG
{
static bool isComposite(int n)
{
if (n <= 1)
return false;
if (n <= 3)
return false;
if (n % 2 == 0 || n % 3 == 0)
return true;
for (int i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return true;
return false;
}
static bool isDigitSumOne(int nm)
{
while (nm > 9)
{
int sum_digit = 0;
while (nm > 0)
{
int digit = nm % 10;
sum_digit = sum_digit + digit;
nm = nm / 10;
}
nm = sum_digit;
}
if (nm == 1)
return true;
else
return false;
}
static void printValidNums(int l, int r)
{
for (int i = l; i <= r; i++)
{
if (isComposite(i) && isDigitSumOne(i))
Console.Write(i + " ");
}
}
static public void Main ()
{
int l = 10, r = 100;
printValidNums(l, r);
}
}
PHP
<?php
function isComposite($n)
{
if ($n <= 1)
return false;
if ($n <= 3)
return false;
if ($n % 2 == 0 || $n % 3 == 0)
return true;
for ($i = 5; $i * $i <= $n; $i = $i + 6)
if ($n % $i == 0 || $n % ($i + 2) == 0)
return true;
return false;
}
function isDigitSumOne($nm)
{
while ($nm > 9)
{
$sum_digit = 0;
while ($nm > 0)
{
$digit = $nm % 10;
$sum_digit = $sum_digit + $digit;
$nm = floor($nm / 10);
}
$nm = $sum_digit;
}
if ($nm == 1)
return true;
else
return false;
}
function printValidNums($l, $r)
{
for ($i = $l; $i <= $r; $i++)
{
if (isComposite($i) && isDigitSumOne($i))
echo $i, " ";
}
}
$l = 10; $r = 100;
printValidNums($l, $r);
?>
Javascript
<script>
function isComposite(n)
{
if (n <= 1)
return false;
if (n <= 3)
return false;
if (n % 2 == 0 || n % 3 == 0)
return true;
for (let i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return true;
return false;
}
function isDigitSumOne(nm)
{
while (nm > 9) {
let sum_digit = 0;
while (nm > 0) {
let digit = nm % 10;
sum_digit = sum_digit + digit;
nm = Math.floor(nm / 10);
}
nm = sum_digit;
}
if (nm == 1)
return true;
else
return false;
}
function printValidNums(l, r)
{
for (let i = l; i <= r; i++) {
if (isComposite(i) && isDigitSumOne(i))
document.write(i + " ");
}
}
let l = 10, r = 100;
printValidNums(l, r);
</script>
Output:
10 28 46 55 64 82 91 100
Time Complexity: O((r – l) * (sqrt(r – l) + log10(r – l)))
Auxiliary Space: O(1)
Optimizations : We can precompute composite numbers using Sieve Algorithms.
program Project1;
uses crt;
var m, i, k, s: integer; //входное число, счётчик, счётчик количества чисел в выходной строке, сумма
//если число простое, эта функция возвращает true,
//если число составное, эта функция возвращает false
//специально не писалась, достал из своей коллекции
function simple(N: integer): boolean;
var i: integer;
begin
if n < 2
then Result := False
else begin
Result := True;
for i:=2 to trunc(sqrt(N)) do
if N mod i = 0
then begin
Result := False;
exit;
end;
end;
end;
//сама программа
begin
repeat
write('Enter M > 1 : '); //ввод M
readln(m);
until m > 1; //если M > 1, то идём дальше, иначе повторяем ввод
s := 0;
k := 1;
writeln('Not simple numbers:');
for i := 2 to m do
if (not simple(i)) then
if (maxint - i) >= s then
begin
s := s + i; //считаем сумму
write(i, ', ');
if k mod 10 = 0 then writeln;
k := k + 1
end
else begin //защита от integer overflow
writeln;
writeln('M is too large!');
readln;
exit;
end;
writeln;
if s > 0 then writeln('Sum of not simple = ', s)
else writeln('All numbers is simple!');
readln;
end.
- Простые числа
- Таблица простых чисел
- Проверка числа на простоту
- Простые числа, примеры и решения
Примеры решения задач
Рассмотрим решения нескольких задач на использование простых чисел. Задачи в основном на доказательство.
СУММА ПРОСТЫХ ЧИСЕЛ
Всегда ли сумма простых чисел – это составное число?
Рассмотрим примеры, чтобы выяснить верно утверждение или нет.
Пример
Возьмем два простых числа: 3 и 5.
Их сумма равна 3 + 5 = 8.
8 – составное число.
Еще пример
Теперь выберем числа 2 и 3.
При сложении 2 + 3 = 5 получили простое число 5.
Сумма простых чисел может быть как простым, так и составным числом
Если углубиться дальше, то можно показать, что сумма большинства простых чисел – это составное число. А если сумма двух простых чисел тоже простое, то одно из слагаемых – число 2. Например:
2 + 5 = 7 – простое число
2 + 11 = 13 – простое число
2 + 29 = 31 – тоже простое.
РАЗНОСТЬ ПРОСТЫХ ЧИСЕЛ
Всегда ли разность простых чисел – это составное число?
Снова приведем примеры
Пример
Возьмем два простых числа: 17 и 5.
Их разность равна 17 – 5 = 12.
12 – составное число.
Пример
Теперь выберем числа 13 и 2.
При вычитании 13 – 2 = 11 получили простое число 11.
Разность простых чисел может быть как простым, так и составным числом
Как и в случае с суммой , разность двух простых чисел – это число простое, если вычитается число 2. Например:
19 – 2 = 17 – простое число
43 – 2 = 41 – простое число
61 – 2 = 59 – тоже простое.
Полезные материалы по теме
- Простые числа
- Таблица простых чисел
- Проверка, простое ли число
