Получить все простые делители числа
Помощь в написании контрольных, курсовых и дипломных работ здесь.
Получить все простые делители числа
Здравствуйте, помогите, пожалуйста. Дано целое число n. Получить все простые делители этого числа.
Получить все делители числа q, взаимно простые с р
3.Даны натуральные числа р и q. Получить все делители числа q, взаимно простые с р заранее спасибо
Получить все простые делители натурального числа
2. Дано натуральное число n. Получить все простые делители этого числа.
Получить все делители числа q, взаимно простые к p
Даны натуральные числа p и q. Получить все делители числа q, взаимно простые к p. помогите .
Для разложения на простые множители можно пользоваться следующим правилом: Путь дано число M = 12376. Разложение на простые множители Берем по очереди простые числа из соответствующей таблицы. И останавливаемся на том — которое является делителем данного числа M. Проводим вертикальную черту. Слева от нее пишем данное число M. Справа простое число которое является делителем. Второй строкой под данным числом M пишем результат деления. И с результатом деления повторяем все снова. Т.е. ищем в таблице простых чисел — делимое. И так до тех пор пока результатом очередного деления не станет число 1.
В результате все числа справа от вертикальной линии — простые множители
Добавлено через 1 минуту
2 3 5 7 11 13 17
19 23 29 31 37 41 43
47 53 59 61 67 71 73
79 83 89 97 101 103 107
109 113 127 131 137 139 149
151 157 163 173 179 181 191
193 197 199
Источник
Получить все простые делители числа
Задача: Дано натуральное число n. Получить все простые делители этого числа.
Объясните пожалуйста как решить эту задачу, т.е. алгоритм действий, т.к. я не очень понимаю как и в каком порядке нужно решать.
Язык программирования не важен, мне главное алгоритм, желательно словами, т.к. я пока только разбираюсь в 2-ух языках: Паскаль и Си.
25 ответов
Задача: Дано натуральное число n. Получить все простые делители этого числа.
Объясните пожалуйста как решить эту задачу, т.е. алгоритм действий, т.к. я не очень понимаю как и в каком порядке нужно решать.
Язык программирования не важен, мне главное алгоритм, желательно словами, т.к. я пока только разбираюсь в 2-ух языках: Паскаль и Си.
1. Найти все простые числа до половины данного числа, для каждого их них проверить делитель или нет.
2. Найти все делители, выбрать из них простые числа.
int cancellation(int divisor,int number);
/************************************************************************
Ведём перебор возможных делителей для number (он будет
лежать в промежутке до корня из number включительно, если
number — сложное, см.http://forum.codenet.ru/
showthread.php?t=40875&page=2 сообщение №18), возможное
значение передаем функции cancellation(); перебор возможных
делителей оптимизирован исключением чисел вида 2k, где
k=1,2,3,4,5,6. ; по предложению cheburator’а возможно
исключение чисел вида 3k, 5k и т.п.
*********************************************************************/
int main()
<
int n,number;
cout >n;
cout
Ну пошевили серым веществом, какое число дает 0 простых делителей?
ЗЫ: правда Draconit не считает их колво.
Ну пошевили серым веществом, какое число дает 0 простых делителей?
ЗЫ: правда Draconit не считает их колво.
ты это вообще к чему?;)
[QUOTE=WidowMaker ]
Ну пошевили серым веществом, какое число дает 0 простых делителей?
ЗЫ: правда Draconit не считает их колво.
[/QUOTE]
1. Ты писал что Draconit пропускает число 3 (в общем случае любое если n простое число);
2. Ты писал Zorkus’у, что выполняя поиск до n/2 мы теряем простое n.
Я указал на то что достаточно ввести счетчик обнаруженных делителей числа, и если он в конце расчетов ==0, то число n — простой делитель самого себя. 😉
1. Ты писал что Draconit пропускает число 3 (в общем случае любое если n простое число);
2. Ты писал Zorkus’у, что выполняя поиск до n/2 мы теряем простое n.
Я указал на то что достаточно ввести счетчик обнаруженных делителей числа, и если он в конце расчетов ==0, то число n — простой делитель самого себя. 😉
😀
мда.
отвечу тебе по пунктам.
1. я знаю и вижу и думаю остальные это видят и знают, а что это разве непонятно? человеку надо вообще-то указать хотя бы пример, чтобы он задумался. а теперь смотри если n=3, то пропускается число 3, которое что? правильно, которое обозначено как n, а значит пропускается n! так что [quote=WidowMaker]пошевили серым веществом[/quote];)
2. это я писал Zorkus’у и ждал ответа от него. мы теряем n по тому подходу, который он предложил и он про счетчик ничего не писал, так что подход неправильный. не следует лезть в разговор, тем более когда видно, что я обращаюсь к определенному собеседнику.
я не совсем тебя понял
ЗЫ: на счет серого вещества (читай подумай), не обижайся, эт я от скуки начинаю хамить;)
[COLOR=»Red»]Что ? От скуки ? Так вот : хамить ты здесь не будешь 😡 ни от скуки , ни от других своих недугов.Поверь мне.Следующее нарушение будет для тебя последним.[/COLOR]
-возведение в степень 2^3=8;
где S_i = 0,1,2,3. кратность простого множителя.
оценим максимальный множитель:
так как P_i
пусть сложилась ситуация, такая что
тогда <(P_k)^S_k>= n (а обычно меньше т.к. знаменатель обычно не равен 1), т.е.
Разве? Вот к примеру число 15, у него 2 простых делителя 3 и 5, но если мы будем искать до значения квадратного корня (а он равен 3,873), то мы упускаем из виду 5. Или я что-то неправильно понял?
А задачку кажется сделал:
#include
#include
#include
using namespace std;
// Алгоритм: ищем простые числа, не превосходящие корня из N. Начинаем с числа 2.
// Для каждого найденного простого проверяем делимость N на него.
// «Вычеркиваем» числа, кратные текущему простому p (вычеркивание начинаем с p^2 и идем до N).
// Ищем следующее невычеркнутое число — это будет следующее простое число.
// И т. д. в цикле, пока не превзошли корня из N.
// Часть из оставшиеся чисел после корня из N могут также быть простыми.
// Таким образом, нужно искать невычеркнутые числа после корня из N и для них также проверять делимость N.
// Ограничимся ста миллионами
#define MAX_VAL 100000000
void main (void)
<
int max_val;
cout > max_val;
if (max_val > MAX_VAL || max_val flags (max_val+1, false); // Массив признаков вычеркнутости чисел.
// flags означает, вычеркнуто ли i или нет (true — вычеркнуто, false — нет).
// Первоначально все числа не перечеркнуты
int current_value = 2; // Текущее простое число
do
<
// Проверим делимость на текущее простое число
if (max_val % current_value == 0)
cout
#include
#include
#include
#include
using namespace std;
// Алгоритм.
// 1 Этап. Ищем простые числа, не превосходящие корня из N. Начинаем с числа 2.
// Для каждого найденного простого проверяем делимость N на него.
// «Вычеркиваем» числа, кратные текущему простому p (вычеркивание начинаем с p^2 и идем до N).
// Ищем следующее невычеркнутое число — это будет следующее простое число.
// И т. д. в цикле, пока не превзошли корня из N.
// 2 Этап. Часть из оставшиеся чисел после корня из N могут также быть простыми.
// Таким образом, нужно искать невычеркнутые числа после корня из N и для них также проверять делимость N.
//
// При нахождении очередного делителя на обоих этапах можно «уменьшить» N,
// т. е. N = N / p (если p — кратный делитель N, делим до тех пор, пока делится),
// чтобы уменьшить количество простых чисел для дальнейшего рассмотрения.
// Ограничимся ста миллионами
#define MAX_VAL 100000000
void main (void)
<
int max_val;
cout > max_val;
if (max_val > MAX_VAL || max_val flags (max_val+1, false); // Массив признаков вычеркнутости чисел.
// flags означает, вычеркнуто ли i или нет (true — вычеркнуто, false — нет).
// Первоначально все числа не перечеркнуты
int current_value = 2; // Текущее простое число
do
<
// Проверим делимость на текущее простое число
if (max_val % current_value == 0)
<
cout flags на char *flags.
нет, это я неправильно написал (недописал). должно быть:
Источник
Найти все делители для заданного числа
Найти все делители для заданного числа:
196708423126676569286001022355850789704717014605805349202544 575890563591254090079162973668806152370560989633700137089767 703775820200092605536123071613442454080946743909994972297960 260325884838413934893551073244410428771253965567859
это программа работает только с маленькими числами
Помощь в написании контрольных, курсовых и дипломных работ здесь.
Процедуры/функции: найти все делители заданного натурального числа и их сумму
Дано натуральное число. Найти все его делители и их сумму Program Stepen_chisla; Var Z, A.
Получить все нечётные делители заданного числа A.
Написать программу получения всех нечётных делителей заданного числа A. Помогите
Найти и вывести все делители числа
Помогите, как проще решить данную задачу. Спасибо.
Найти все делители натурального числа n.
Найти все делители натурального числа n. Решение pascal ABC
Artyom2124, зачем тебе все делители для этого числа? что ты с ними будешь делать?
но, если реально нужны — то длинная арифметика тебе в помощь!
а сколько уже нашли?
могу 268 делителей скинуть.
Лучше конечно искать за О(sqrt(n)), но и так работает
Mike_Boone, в Pascal ABC Ваш код на Pascal ABC.NET работать не будет.
И ещё. Если публикуете программу на диалекте языка, который отличается от диалекта языка в названии раздела, то указывайте, на каком именно диалекте языка написана Ваша программа.
Ничего страшного, вообще-то.
Если считаете, что Ваш ответ поможет ТС, то можете писать в Pascal ABC и на Pascal ABC.NET, поскольку у всех, как правило, установлен Pascal ABC.NET, потому что древний Pascal ABC сейчас даже найти не так уж и легко. С другой стороны, есть одна несуразность: в большинстве учебных заведений учат «классическому» паскалю (как правило, Turbo Pascal), а в качестве среды программирования рекомендуют Pascal ABC.NET, потому что он бесплатный и запускается в современных Windows без танцев с бубном. Порой даже и не подозревая, что Pascal ABC.NET и старичок Pascal ABC, от которого Pascal ABC.NET произошёл — это далеко не одно и то же.
Короче, может случиться нелепое недопонимание. Поэтому делайте приписку типа «Программа для Pascal ABC.NET».
Artyom2124, Вы уверены? Если программа будет выдавать по 1000 делителей в секунду, она будет работать более месяца, и, если делители записывать в текстовый файл, конечный объём файла будет примерно 160 гигабайт (более 170000000000 символов). Сильно сомневаюсь, что такое задание могли дать в каком-либо учебном заведении.
Artyom2124, может быть, нужно найти все простые делители?
Это я сделал. К счастью, максимальный простой делитель Вашего числа сравнительно маленький, и помещается в тип integer. Общее количество делителей числа не помещается в тип integer, для подсчёта указанной величины я использовал тип real.
Программа факторизации Вашего числа, находит все простые делители, их максимальные степени и общее количество делителей числа:
На моём древнем ноутбуке в Pascal ABC программа считает примерно 24 секунды, эта же программа, подрихтованная и запущенная в Free Pascal, считает примерно 4 секунды.
| Прогон программы |
Первая колонка — номер простого делителя, вторая — величина простого делителя, третья — максимальная степень, при возведении в которую простого делителя, получившееся число всё ещё делит исходное число нацело.
Ниже таблицы — общее количество всех делителей.
Пояснения по количеству делителей: любой делитель числа может быть представлен в виде произведения степеней всех простых делителей числа, степень при конкретном простом делителе может быть от 0 до упомянутой выше максимальной степени. Таким образом, общее количество делителей равно количеству всех возможных комбинаций степеней при всех простых делителях, иными словами, произведению увеличенных на 1 максимальных степеней для каждого простого делителя.
Напоследок, если строго по заданию. Казалось бы, имеет смысл дописать мою программу. Осталось совсем немного: перебрать все степени при простых делителях, и умножить исходную единицу нужное количество раз на каждый простой делитель, и так 2963520000 раз. Короче, сущий пустяк, думаю, за год можно будет найти все делители заданного числа.
Добавлено через 2 часа 3 минуты
Если желаете, можете
хоть вручную. Сначала принимаете все степени равными 0, и получаете первый делитель:
28513 0 27943 0 26591 0 23563 0 20411 0 18541 0 17681 0 16417 0 16223 0 15161 0 12547 0 10799 0 6959 0 5651 0 1297 0
=1
Затем начинаем увеличивать степени, например, в порядке справа налево, и перебираем все возможные комбинации следующим образом: если степень в самом правом сомножителе достигла максимальной по таблице, то обнуляем эту степень, и увеличиваем следующую (вторую справа), и продолжаем в том же духе до тех пор, пока не переполнится и вторая справа степень, тогда увеличиваем третью справа, а вторую справа обнуляем, и так до тех пор, пока набор степеней не будет такой же, как в таблице:
28513 0 27943 0 26591 0 23563 0 20411 0 18541 0 17681 0 16417 0 16223 0 15161 0 12547 0 10799 0 6959 0 5651 0 1297 1
=1297
28513 0 27943 0 26591 0 23563 0 20411 0 18541 0 17681 0 16417 0 16223 0 15161 0 12547 0 10799 0 6959 0 5651 0 1297 2
=1682209
28513 0 27943 0 26591 0 23563 0 20411 0 18541 0 17681 0 16417 0 16223 0 15161 0 12547 0 10799 0 6959 0 5651 0 1297 3
=2181825073
28513 0 27943 0 26591 0 23563 0 20411 0 18541 0 17681 0 16417 0 16223 0 15161 0 12547 0 10799 0 6959 0 5651 0 1297 4
=2829827119681
28513 0 27943 0 26591 0 23563 0 20411 0 18541 0 17681 0 16417 0 16223 0 15161 0 12547 0 10799 0 6959 0 5651 0 1297 5
=3670285774226257
28513 0 27943 0 26591 0 23563 0 20411 0 18541 0 17681 0 16417 0 16223 0 15161 0 12547 0 10799 0 6959 0 5651 0 1297 6
=4760360649171455329
28513 0 27943 0 26591 0 23563 0 20411 0 18541 0 17681 0 16417 0 16223 0 15161 0 12547 0 10799 0 6959 0 5651 1 1297 0
=5651
28513 0 27943 0 26591 0 23563 0 20411 0 18541 0 17681 0 16417 0 16223 0 15161 0 12547 0 10799 0 6959 0 5651 1 1297 1
=7329347
.
28513 0 27943 0 26591 0 23563 0 20411 0 18541 0 17681 0 16417 0 16223 0 15161 0 12547 0 10799 0 6959 0 5651 1 1297 6
=26900798028467894064179
28513 0 27943 0 26591 0 23563 0 20411 0 18541 0 17681 0 16417 0 16223 0 15161 0 12547 0 10799 0 6959 0 5651 2 1297 0
=31933801
.
28513 0 27943 0 26591 0 23563 0 20411 0 18541 0 17681 0 16417 0 16223 0 15161 0 12547 0 10799 0 6959 0 5651 2 1297 6
=152016409658872069356675529
28513 0 27943 0 26591 0 23563 0 20411 0 18541 0 17681 0 16417 0 16223 0 15161 0 12547 0 10799 0 6959 1 5651 0 1297 0
=6959
.
28513 0 27943 0 26591 0 23563 0 20411 0 18541 0 17681 0 16417 0 16223 0 15161 0 12547 0 10799 0 6959 1 5651 2 1297 6
=1057882194816090730653105006311
.
28513 3 27943 1 26591 7 23563 6 20411 6 18541 4 17681 4 16417 4 16223 1 15161 4 12547 1 10799 2 6959 5 5651 2 1297 6
=19670842312667656928600102235585078970471701460580534920254 457589056359125409007916297366880615237056098963370013708976 770377582020009260553612307161344245408094674390999497229796 0260325884838413934893551073244410428771253965567859
Добавлено через 4 часа 36 минут
Хотя. Если применить что-нибудь получше строк, то. Программа на Free Pascal Compiler для печати заданного количества делителей, начиная с делителя с заданным номером:
Источник
