Как найти наименьший натуральный делитель отличный от 1
Перейти к содержимому

Как найти наименьший натуральный делитель отличный от 1

  • автор:

Решение задачи №1126 «Минимальный делитель» с ACMP

Требуется найти наименьший натуральный делитель целого числа N, отличный от 1.

Входные данные
Входной файл INPUT.TXT содержит целое число N (1 < N ≤ 106).

Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.

Решение на C++
#include
using namespace std;
main()
int n,i=2;
cin>>n;
while (n%i)i++;
cout >

Условия задач взяты с сайта acmp.ru

«izilearn.ru» © 2018 — 2024. Связь с администрацией — izilearn@mail.ru

Минимальный делитель

Найдите самый маленький натуральный делитель числа x, отличный от 1. Входные данные: Вводится натуральное число x(2

x = int(input()) for i in range(2, x + 1): if x % i == 0: print(i) break 

Отслеживать

304 1 1 серебряный знак 13 13 бронзовых знаков

задан 5 ноя 2019 в 3:22

nikobellic nikobellic

335 6 6 золотых знаков 10 10 серебряных знаков 18 18 бронзовых знаков

print(next(i for i in range(2, x + 1) if x % i == 0)) .

3 сен 2023 в 20:00

2 ответа 2

Сортировка: Сброс на вариант по умолчанию

function smallestDivider(n) < if (n % 2 == 0) return 2; var d = 3, stop = Math.sqrt(n); while (n % d && d console.log(961, smallestDivider(961)); console.log(97, smallestDivider(97)); console.log(1027, smallestDivider(1027)); console.log(29999, smallestDivider(29999));
function smallestDivider(n) < if (n % 2 == 0) return 2; var stop = Math.sqrt(n); for (var d = 3; d console.log(961, smallestDivider(961)); console.log(97, smallestDivider(97)); console.log(1027, smallestDivider(1027)); console.log(29999, smallestDivider(29999));

Анализ алгоритма

Переберем делители числа n от 2 до и выведем минимальный . Если делителей в интервале [2; ] не оказалось, то ответом будет само число n .

Если n = 21, то его наименьшим делителем будет 3.

Если n = 13 (простое число) , то его наименьшим делителем будет 13.

Читаем входное значение n .

Установим flag = 0. Перебираем возможные делители от 2 до . При нахождении первого же (наименьшего) делителя устанавливаем flag = 1 , выводим делитель и выходим из цикла.

Если делитель не был найден, то число n простое. Выводим его.

if (flag == 0) printf( "%d\n" , n);

import java.util.*;

class Main

public static void main(String[] args )

Scanner con = new Scanner(System. in );

int n = con .nextInt();

int flag = 0;

if ( n % i == 0)

System. out .println( i );

if ( flag == 0) System. out .println( n );

import math

for i in range ( 2 , math.isqrt(n)+ 1 ):

if n % i == 0 :

else : # сюда попадем когда цикл закончится сам

Найти наименьший делитель числа, отличный от 1

Author24 — интернет-сервис помощи студентам

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

Пыталась, написала так, только получается не наименьший делитель, а все возможные делители отличные от 1 :с

1 2 3 4 5 6
n = int(input()) i = 1 while i  n: i = i + 1 if n % i == 0: print(i)

Помогите решить, чтоб выводило только наименьший
Лучшие ответы ( 2 )
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:

Для любого целого числа найти его наименьший и наибольший делитель
Написать программу. Для любого целого числа найти его наименьший и наибольший делитель (1 и само.

Наименьший простой делитель числа
Дано целое число, не меньшее 2. Выведите его наименьший простой делитель. На вход целое число N<=.

Наименьший простой делитель данного натурального числа
# TASK # Найти наименьший простой делитель данного натурального числа. a = int (input.

Найти наименьший натуральный делитель целого числа N, отличный от 1
Минимальный делитель Требуется найти наименьший натуральный делитель целого числа N, отличный от.

33 / 30 / 16
Регистрация: 21.01.2014
Сообщений: 101

Лучший ответ

Сообщение было отмечено mik-a-el как решение

Решение

Ну, как бы всё очевидно - нужно всего лишь выйти из цикла при обнаружении первого (он и есть наименьший) делителя:

1 2 3 4 5
while i  n: i = i + 1 if n % i == 0: print(i) break

Регистрация: 07.09.2017
Сообщений: 27

Спасибо) Упс, забыла про break Просто на курсе объяснялось, что эту команду лучше не использовать, или здесь больше нет вариантов?

Эксперт PythonЭксперт JavaЭксперт CЭксперт С++

12461 / 7485 / 1754
Регистрация: 25.07.2009
Сообщений: 13,764

ЦитатаСообщение от Riita Посмотреть сообщение

Просто на курсе объяснялось, что эту команду лучше не использовать

Как-нибудь обосновывали, или нужно было на слово поверить?

ЦитатаСообщение от Riita Посмотреть сообщение

или здесь больше нет вариантов?

1 2 3 4 5 6 7 8 9 10
>>> def min_divider(n, d=2): . return d if n % d == 0 else min_divider(n, d + 1) . >>> min_divider(6) 2 >>> min_divider(7) 7 >>> min_divider(25) 5 >>>

только надо убедиться, что переданное число не меньше двух.
Регистрация: 07.09.2017
Сообщений: 27

Ну вот решила поверить, думала люди создавшие видео-курс говорят только правильные вещи и надо их беспрекословно слушать 😀
Я это еще не прошла, дошла только до цикла while пока, спасибо 🙂

Эксперт PythonЭксперт JavaЭксперт CЭксперт С++

12461 / 7485 / 1754
Регистрация: 25.07.2009
Сообщений: 13,764

Лучший ответ

Сообщение было отмечено mik-a-el как решение

Решение

ЦитатаСообщение от Riita Посмотреть сообщение

Ну вот решила поверить
"Верить нельзя никому, даже самому себе! Мне можно. " (с)

ЦитатаСообщение от Riita Посмотреть сообщение

дошла только до цикла while

1 2 3 4 5 6 7 8 9
>>> n = int(input("Number greater than 1: ")) Number greater than 1: 625 >>> i = 2 >>> while n % i: . i += 1 . >>> print(i) 5 >>>

Регистрация: 07.09.2017
Сообщений: 27

Эм, не пойму почему после n % 1 нет = и какого-то результата и как в принципе работает этот код, что он дает правильный ответ? ._.

33 / 30 / 16
Регистрация: 21.01.2014
Сообщений: 101
не пойму почему после n % 1 нет = и какого-то результата
n % i эквивалентно n % i == 1
Регистрация: 07.09.2017
Сообщений: 27
Ааа, теперь ясно, буду знать

Эксперт PythonЭксперт JavaЭксперт CЭксперт С++

12461 / 7485 / 1754
Регистрация: 25.07.2009
Сообщений: 13,764

ЦитатаСообщение от Riita Посмотреть сообщение

Ааа, теперь ясно, буду знать
Немного не так: результат выражения равный нулю трактуется как False, неравный - True
Регистрация: 01.01.2019
Сообщений: 2

Начала изучать Python, помогите пожалуйста, с поиском ошибки в задачи. Система выдает сообщение на 14 тесте: "Превышено максимальное время работы" и оценивает 13 баллов из 100

1 2 3 4 5
n=int(input()) i = 2 while n%i!=0: i+= 1 print(i)

Регистрация: 01.01.2019
Сообщений: 2

Пересмотрела все варианты которые выше и в похожых темах, этот ответ система оценила наибольшим количеством балов 13.
Другие варианты оценивает на 6 баллов или 0.

Эксперт PythonЭксперт JavaЭксперт CЭксперт С++

12461 / 7485 / 1754
Регистрация: 25.07.2009
Сообщений: 13,764

ЦитатаСообщение от tana256 Посмотреть сообщение

"Превышено максимальное время работы"

Вообще для интерпретируемого языка проблема скорее надуманная. Но в принципе можно и ускорить.
Если известно максимально возможное число и можно выполнять инициализирующий код, нужно составить список из простых чисел начиная с 2 и до квадратного корня из максимально возможного значения включительно. Заданное число проверять на делимость на простые числа - так будет заметно быстрее.
Можно немного ускорить проверив сначала число на чётность, а при отрицательном результате делить только на нечётные числа. Способ далёк от идеального - если число не делится на 5 (к примеру), то и на 15 оно точно не разделится, но всё-таки нечётных чисел значительно меньше.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *