Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 9 ] 
Автор Сообщение
 Заголовок сообщения: Простые числа
СообщениеДобавлено: 14 сен 2018, 18:56 
Не в сети
Начинающий
Зарегистрирован:
14 сен 2018, 18:39
Сообщений: 2
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Всем привет! Задание по программированию. Короче, есть простые числа, каждое из которых возводится в какую-либо степень (степерь может быть больше 10 000 000). При перемножении всех этих простых чисел получается число N. Необходимо пройтись по каждому из чисел k из диапазона [0...N] и понять, является ли НОД числа k и соответствующего небольшого случайного числа единицей или другим числом. Хотел бы понять, есть ли какие-либо закономерности при перемножении простых чисел, при помощи которых можно было бы решить данное задание. Или же можно сделать какие-то выводы, обрабатывая N в первоначальном, разложенном виде?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Простые числа
СообщениеДобавлено: 14 сен 2018, 19:29 
Не в сети
Beautiful Mind
Аватара пользователя
Зарегистрирован:
09 авг 2018, 23:20
Сообщений: 1011
Cпасибо сказано: 32
Спасибо получено:
121 раз в 116 сообщениях
Очков репутации: 8

Добавить очки репутацииУменьшить очки репутации
Что такое "соответствующее небольшое число"?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Простые числа
СообщениеДобавлено: 14 сен 2018, 20:07 
Не в сети
Начинающий
Зарегистрирован:
14 сен 2018, 18:39
Сообщений: 2
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Число, которое в зависимости от длины исходного массива бинарных чисел, полученного в задании для одного из вариантов простых чисел, варьируется от 1 до приблизительно 30

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Простые числа
СообщениеДобавлено: 14 сен 2018, 20:14 
Не в сети
Beautiful Mind
Аватара пользователя
Зарегистрирован:
09 авг 2018, 23:20
Сообщений: 1011
Cпасибо сказано: 32
Спасибо получено:
121 раз в 116 сообщениях
Очков репутации: 8

Добавить очки репутацииУменьшить очки репутации
Разлагаем это число на простые. Смотрим, сколько из этого набора включено в [math]k[/math]. Перемножаем эти общие множители, получаем НОД.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Простые числа
СообщениеДобавлено: 14 сен 2018, 20:59 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
atlakatl писал(а):
Необходимо пройтись по каждому из чисел k из диапазона [0...N]


Долго рассказывать про это N, а в итоге это нафиг совсем не нужно. Природа этого N вообще не важна при такой постановке. Ну кроме того, что вряд ли вы сможете пройтись более чем по [math]10^{10}[/math] числам.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Простые числа
СообщениеДобавлено: 14 сен 2018, 21:15 
Не в сети
Beautiful Mind
Аватара пользователя
Зарегистрирован:
09 авг 2018, 23:20
Сообщений: 1011
Cпасибо сказано: 32
Спасибо получено:
121 раз в 116 сообщениях
Очков репутации: 8

Добавить очки репутацииУменьшить очки репутации
swan
Чем я Вас достал, что Вы приписываете мне чужие слова и пытаетесь выглядеть по-отечески устало и мудро?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Простые числа
СообщениеДобавлено: 17 сен 2018, 10:16 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
atlakatl, прошу прощения. Я лишь выделил цитату, а местный движок зачем-то вас процитировал, а я не уследил.
Но, право же, задача мне непонятна. Какой смысл описывать свойства верхней границы, если нам надо проверять все числа отрезка?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Простые числа
СообщениеДобавлено: 17 сен 2018, 11:22 
Не в сети
Light & Truth
Зарегистрирован:
28 мар 2014, 23:59
Сообщений: 6312
Cпасибо сказано: 633
Спасибо получено:
509 раз в 477 сообщениях
Очков репутации: 47

Добавить очки репутацииУменьшить очки репутации
Maxoff писал(а):
Хотел бы понять, есть ли какие-либо закономерности при перемножении простых чисел, при помощи которых можно было бы решить данное задание. Или же можно сделать какие-то выводы, обрабатывая N в первоначальном, разложенном виде


Как ни рассматривай Ваше задание, никакие известные закономерности, даже если они и возникают при перемножении простых чисел, не помогут его решить. Ведь Вы рассматриваете не только получившееся при перемножении степеней простых число, но и все натуральные числа меньше него. А у них другая факторизация.

Придется решать в лоб, найти все делители "некоторого" маленького числа и начиная с самого большого делителя, методом перебора определить НОД с некоторым [math]k\in[0,N][/math], деля это k и проверяя остаток, а можно факторизовать k и сравнивать факторы, но это будет более ресурсозатратно. Что-то определенное Вы можете сказать лишь о числе k=N, сравнив его известную факторизацию с факторизацией "некоторого" числа.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Простые числа
СообщениеДобавлено: 26 сен 2018, 19:49 
Не в сети
Последняя инстанция
Зарегистрирован:
17 окт 2013, 19:46
Сообщений: 1377
Cпасибо сказано: 108
Спасибо получено:
561 раз в 447 сообщениях
Очков репутации: 155

Добавить очки репутацииУменьшить очки репутации
Maxoff писал(а):
Задание по программированию. Короче, есть простые числа, каждое из которых возводится в какую-либо степень (степерь может быть больше 10 000 000). При перемножении всех этих простых чисел получается число N. Необходимо пройтись по каждому из чисел k из диапазона [0...N] и понять, является ли НОД числа k и соответствующего небольшого случайного числа единицей или другим числом
В заданиях по программированию обычно требуется что-то ввести и что-то вывести. Как понимать слово "Понять"?
Для всех чисел из диапазона вывести НОД? Вряд ли - возраст вселенной не хватит. Так что нужно сделать? Вывести количество взаимнопростых с N? (или не взаимнопростых). Тогда дело в шляпе.

Цитата:
Необходимо пройтись по каждому из чисел k из диапазона [0...N]
И сколько время уйдет только на это??? При таких N?

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 9 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Простые числа

в форуме Алгебра

mad_math

43

2276

06 ноя 2014, 15:57

Простые числа

в форуме Теория чисел

alex_D

2

634

04 апр 2016, 11:01

Простые числа

в форуме Алгебра

vkid_velikii

9

291

12 ноя 2021, 21:16

Простые числа

в форуме Алгебра

Ne5tir

5

223

22 дек 2020, 17:12

Простые числа

в форуме Палата №6

nino4554

59

1820

27 дек 2017, 19:58

Простые числа

в форуме Размышления по поводу и без

ammo77

29

852

25 июл 2019, 11:01

Простые числа

в форуме Теория чисел

Diego_D

8

648

29 мар 2016, 17:31

Простые числа

в форуме Размышления по поводу и без

Galina Alexandrovna

2

489

03 авг 2017, 20:06

Простые числа

в форуме Теория чисел

vorvalm

172

5022

08 фев 2016, 10:24

Простые числа

в форуме Теория чисел

Galina Alexandrovna

15

1723

14 мар 2019, 20:22


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: Yandex [bot] и гости: 41


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved