Как найти наименьший делитель заданного числа - Исправление недочетов и поиск решений вместе с Examum.ru

Improve Article

Save Article

Like Article

Read

Discuss

Improve Article

Save Article

Like Article

Given a number N, find the smallest prime divisor of N.

Examples:

Input: 25
Output: 5

Input: 31
Output: 31

Approach:

Check if the number is divisible by 2 or not.
Iterate from i = 3 to sqrt(N) and making a jump of 2.
If any of the numbers divide N then it is the smallest prime divisor.
If none of them divide, then N is the answer.

Below is the implementation of the above algorithm:

C++

#include <bits/stdc++.h>

using namespace std;

int smallestDivisor(int n)

{

if (n % 2 == 0)

return 2;

for (int i = 3; i * i <= n; i += 2) {

if (n % i == 0)

return i;

}

return n;

}

int main()

{

int n = 31;

cout << smallestDivisor(n);

return 0;

}

Java

import java.io.*;

class GFG {

static int smallestDivisor(int n)

{

if (n % 2 == 0)

return 2;

for (int i = 3; i * i <= n; i += 2) {

if (n % i == 0)

return i;

}

return n;

}

public static void main (String[] args) {

int n = 31;

System.out.println (smallestDivisor(n));

}

Python3

def smallestDivisor(n):

if (n % 2 == 0):

return 2;

i = 3;

while(i * i <= n):

if (n % i == 0):

return i;

i += 2;

return n;

n = 31;

print(smallestDivisor(n));

C#

using System;

class GFG

{

static int smallestDivisor(int n)

{

if (n % 2 == 0)

return 2;

for (int i = 3;

i * i <= n; i += 2)

{

if (n % i == 0)

return i;

}

return n;

}

static public void Main ()

{

int n = 31;

Console.WriteLine(smallestDivisor(n));

}

PHP

<?php

function smallestDivisor($n)

{

if ($n % 2 == 0)

return 2;

for ($i = 3; $i * $i <= $n; $i += 2)

{

if ($n % $i == 0)

return $i;

}

return $n;

}

$n = 31;

echo smallestDivisor($n);

?>

Javascript

<script>

function smallestDivisor(n) {

if (n % 2 == 0)

return 2;

for (var i = 3; i * i <= n; i += 2) {

if (n % i == 0)

return i;

}

return n;

}

var n = 31;

document.write(smallestDivisor(n));

</script>

Time Complexity: O(sqrt(N)), as we are using a loop to traverse sqrt (N) times. As the condition is i*i<=N, on application of sqrt function on both the sides we get sqrt (i*i) <= sqrt(N), which is i<= sqrt(N), therefore the loop will traverse for sqrt(N) times.

Auxiliary Space: O(1), as we are not using any extra space.

Last Updated :
13 Jun, 2022

Like Article

Save Article

Источник

Как находить наименьший делитель в итеративном процессе рекурсии?

Прохожу курс основ программирования на Хекслете.
В задачке по итеративному процессу, где надо найти наименьший делитель заданного числа случился хардстак. Вот мой код:

const smallestDivisor = (num) => {
const iter = (counter, acc) => {
    if (counter === 1) {
        return 1;
}
    if (counter % acc) {
        return acc;
    }
    return iter(counter, acc + 1);
};
    return iter(num, 4);
};

Пытаюсь найти наименьший делитель для числа 4, который является 2кой.
Спойлерить решение от Хекслета не хочу, хочу понять как решать.

Вопрос задан

более трёх лет назад
2426 просмотров

Пригласить эксперта

Читайте задание внимательнее.
Попробуйте в голове разложить алгоритм простыми словами.

1. Передаем в функцию число num (например, 9)
2. Создаем переменную acc с начальным значением 2 (1 нам не нужно)
3. Делим num на acc.
4. Делиться без остатка? (9 % 2) Это наименьший делитель, возвращаем его.
5. Не делиться? Добавляем к acc +1 и пробуем еще раз.
6. Дошли до acc = num? Возвращаем num.

Соответственно, с пункта 2 по 6 — это рекурсия, которая работает с acc.

Показать ещё
Загружается…

25 мая 2023, в 17:40

1 руб./за проект

25 мая 2023, в 17:10

1500 руб./в час

25 мая 2023, в 17:00

20000 руб./за проект

Минуточку внимания

Источник

Прохожу уроки на Hexlet и столкнулся с темой «итеративный процесс«.
Думаю, что в моем коде (см. ниже) не хватает ещё нескольких условий (инструкций) для его грамотного выполнения.

Не прошу выполнить всё за меня, но прошу дать наводку или объяснить, чего не хватает. ГОТОВЫЙ КОД МНЕ НЕ НУЖЕН!

const nod = (num) => {
  const iter = (delitel, acc) => {
    if (delitel === 1) {
      return acc
    }
    return iter(delitel - 1, acc % delitel)
  }
  return iter(5, num)
}
console.log(nod(15));

задан 28 янв 2019 в 10:42

const nd = (num, div = 1) => num % ++div ? nd(num, div) : div;

console.log(nd(15));

ответ дан 28 янв 2019 в 12:45

С помощью рекурсии это можно сделать так

const node = (num) => {
  const iter = (divider = 2) => {
    if (divider * divider > num) {
      return num;
    }
    if (num % divider) {
      return iter(divider + 1);
    }
    return divider;
  }
  return iter();
}
console.log(node(15));

ответ дан 28 янв 2019 в 12:03

VladimirVladimir

1,6977 серебряных знаков6 бронзовых знаков

Как я помню из SICP итеративный процесс это рекурсия в которой рекурсивный вызов — последнее действие в функции. Это ещё называется хвостовая рекурсия.

Тогда задачу можно решить например так:

const least_divisor = n => {
    const iter = d => {
        if (n % d === 0) {
            return d;
        }
        return iter(d + 1);
    }
    return iter(2);
};

Хвостовая рекурсия в функции с говорящим названием iter.

Или можно перебирать делители с другого конца. Выглядит странно, но работает:

const least_divisor = n => {
    const iter = (d, least_d) => {
        if (d === 1) {
            return least_d;
        }
        if (n % d === 0) {
            least_d = d;
        }
        return iter(d - 1, least_d);
    }
    return iter(n - 1, n);
};

ответ дан 27 мая 2021 в 22:49

const smallestDivisor = (num) => {
  if (num % 2 === 0 && num > 0) {
    return 2;
  } else if (num <= 0) {
    return NaN;
  } else if (num === 1) {
    return num;
  }
  // Проверки на корректный ввод данных для значения "num"
  const devider = (count = 2) => {
    /* Если "Num" делится на значение "devider" с остатком 
       (остаток от деления не равен 0,  к значению делителя 
       прибовляем (+1) */
    if (num % count !== 0) {
      return devider(count + 1);
    } else {
      /* Дефолтное значение (если остаток от деления равен 0, 
         count остается прежним) */
      return count;
    }
  }
  return devider();
}

0xdb

51.4k194 золотых знака56 серебряных знаков232 бронзовых знака

ответ дан 25 янв 2022 в 15:02

Евгений КолмакЕвгений Колмак

4732 золотых знака3 серебряных знака13 бронзовых знаков

Источник

crushed00

2 / 2 / 5

Регистрация: 02.12.2019

Сообщений: 249

02.12.2019, 20:07. Показов 12970. Ответов 4

Метки нет (Все метки)

Дано целое число, не меньшее 2. Выведите его наименьший натуральный делитель, отличный от 1.

Формат входных данных

Вводится целое положительное число.

Формат выходных данных

Выведите ответ на задачу.

Sample Input:15

Sample Output:3

using System;
namespace Convertator
{
    class Program
    {
        static void Main(string[] args)
        {
            int a, i;
            Console.Write("Введите натуральное число не меньше двух: ");
            i = Convert.ToInt32(Console.ReadLine());
 
            while (a >= 2; i <= a; i++)
            {
                if (a % i == 0)
                {
                    Console.WriteLine(i);
                    break;
                }
               
 
                Console.ReadKey();
            }
        }
    }
}

Programming Эксперт 94731 / 64177 / 26122 Регистрация: 12.04.2006 Сообщений: 116,782	02.12.2019, 20:07
4

crushed00

2 / 2 / 5

Регистрация: 02.12.2019

Сообщений: 249

02.12.2019, 20:15

[ТС]

Дано целое число, не меньшее 2. Выведите его наименьший натуральный делитель, отличный от 1.

using System;
namespace Convertator
{
    class Program
    {
        static void Main(string[] args)
        {
            int a, i;
            Console.Write("Введите натуральное число не меньше двух: ");
            i = Convert.ToInt32(Console.ReadLine());
 
            while (a >= 2; i <= a; i++)
            {
                if (a % i == 0)
                {
                    Console.WriteLine(i);
                    break;
                }
               
 
                Console.ReadKey();
            }
        }
    }
}

Где ошибка?

Элд Хасп

Модератор

13780 / 9992 / 2661

Регистрация: 21.04.2018

Сообщений: 29,763

Записей в блоге: 2

02.12.2019, 20:22

crushed00

using System;
namespace Convertator
{
    class Program
    {
        static void Main(string[] args)
        {
            int a = 2, i;
            Console.Write("Введите натуральное число не меньше двух: ");
            i = Convert.ToInt32(Console.ReadLine());
 
            while (a*a <= i )
            {
                if (a % i == 0)
                {
                    Console.WriteLine(i);
                    break;
                }
                a++;
           }
           Console.ReadKey();
        }
    }
}

Catstail

Модератор

35427 / 19452 / 4071

Регистрация: 12.02.2012

Сообщений: 32,488

Записей в блоге: 13

02.12.2019, 20:50

using System;
 
public class Test
{
    public static void Main()
    {
      int a, i;
      Console.Write("Введите натуральное число не меньше двух: ");
       a = Convert.ToInt32(Console.ReadLine());
       for (i=2; i*i <= a; i++)
       {
           if (a % i == 0)
          {
              Console.WriteLine(i);
              break;
          }
 
          Console.ReadKey();
       }
   }
}

VladisSVostok

4 / 4 / 0

Регистрация: 15.09.2019

Сообщений: 79

28.01.2023, 01:05

            int a, i;
            bool found = false;
            a = Convert.ToInt32(Console.ReadLine());
            for (i = 2; i * i <= a; i++) {
                if (a % i == 0) {
                    found = true;
                    break;
                }
            }
 
            if (!found) {
                Console.Write(a);
            }
            else {
                Console.Write(i);
            }

IT_Exp Эксперт 87844 / 49110 / 22898 Регистрация: 17.06.2006 Сообщений: 92,604	28.01.2023, 01:05
5

Источник

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters

Show hidden characters

	const smallestDivisor = (num) => {
	const iter = (acc) => {
	// We use ‘num / 2’ in the condition below, and not ‘num’.
	// This is a simple optimization: a number cannot be divided
	// by a number larger than its half.
	if (acc > num / 2) {
	return num;
	}
	if (num % acc === 0) {
	return acc;
	}
	return iter(acc + 1);
	};

	return iter(2);
	// END
	}
	export default smallestDivisor;


	smallestDivisor.js
	Реализуйте тело функции smallestDivisor, используя итеративный процесс. Эта функция должна находить наименьший делитель заданного числа.

	Доп. условия: число, передаваемое в функцию, больше нуля; делитель должен быть больше единицы, за исключением случая, когда аргументом является единица (наименьшим делителем которой является также единица).

	Например, наименьший делитель числа 15 это 3.

	smallestDivisor(15); // 3
	smallestDivisor(17); // 17
	Идея алгоритма:

	Попробуйте разделить число на 2.
	Если число делится без остатка, то это наименьший делитель.
	Если нет, то попробуйте следующий делитель.
	Если ничего не делит число без остатка, то переданное число является простым, так что его наименьший делитель — оно само (не считая 1)
	Подсказка
	Вспомните про оператор % (modulus or остаток от деления) из урока 4. Он вычисляет остаток от деления одного операнда на другой. Например, 11%5 это 1, а 10%2 это 0.

	Так что если x%y это 0, то y делит x без остатка.

Источник