Форум программистов, компьютерный форум CyberForum.ru

Самый большой простой делитель числа - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
Outmee
 Аватар для Outmee
2 / 2 / 0
Регистрация: 26.01.2014
Сообщений: 56
11.03.2014, 20:37     Самый большой простой делитель числа #1
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
 
using namespace std;
 
void main()
{
    setlocale(LC_ALL, "Russian");
 
    cout << "Найдите самый большой делитель сложного числа, являющийся простым числом." << endl;
    int numb = 0;
    int del = 0;
    int z = 0;
    cin >> numb;
 
    for (int i = 3; i < numb; i++)
        if (numb%i == 0 )
        {
            z = 0;
            for (int b = 0; b < i; b++)
            {
                if (i%b == 0) z++;
                else;
            }
            if (z > 2) del = i;
                
        }
    cout << "самый большой, простой делитель числа " << del << endl;
    system("pause");
}
как я только не жонглировал с числами, все равно пишет не то.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.03.2014, 20:37     Самый большой простой делитель числа
Посмотрите здесь:

Самый самый самый простой пример рекурсии C++
C++ найти самый большой элемент Массива
самый, самый большой )) C++
C++ найти максимальный простой делитель числа
C++ Самый простой вопрос на сегодня.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zer0mail
2187 / 1870 / 187
Регистрация: 03.07.2012
Сообщений: 6,658
Записей в блоге: 1
11.03.2014, 21:16     Самый большой простой делитель числа #2
Надо не жонглировать числами, а придумать алгоритм и реализовать его.
Опиши словами алгоритм, который хотел запрограммировать.
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,056
11.03.2014, 21:33     Самый большой простой делитель числа #3
Цитата Сообщение от Outmee Посмотреть сообщение
for (int i = 3; i < numb; i++)
делитель не может быть больше половины
простое число не может быть четным( исключая двойку)
исходя из этого
цикл можно уменьшить
C++
1
for (int i = 3; i < numb/2; i+=2)
далее проверяй i на простоту, на форуме куча тем про это

Добавлено через 1 минуту
Цитата Сообщение от Outmee Посмотреть сообщение
if (z > 2) del = i;
2 это тоже простое число
zer0mail
2187 / 1870 / 187
Регистрация: 03.07.2012
Сообщений: 6,658
Записей в блоге: 1
11.03.2014, 21:51     Самый большой простой делитель числа #4
Цитата Сообщение от ValeryS Посмотреть сообщение
делитель не может быть больше половины
Но ровно половиной - может . Правильный алгоритм - быстрый поиск простых чисел с одновременной проверкой, делится ли X на новое простое число (и уменьшением X, если делится).
Новичок
Модератор
 Аватар для Новичок
1141 / 712 / 148
Регистрация: 17.07.2012
Сообщений: 4,044
Записей в блоге: 1
Завершенные тесты: 2
11.03.2014, 22:04     Самый большой простой делитель числа #5
По моему достаточно перебирать делители до округленного корня квадратного.

Добавлено через 3 минуты
Хотя не, не все делители-то простыми будут. Мне кроме решения в лоб ничего не приходит в голову.
Цитата Сообщение от zer0mail Посмотреть сообщение
Правильный алгоритм - быстрый поиск простых чисел с одновременной проверкой, делится ли X на новое простое число (и уменьшением X, если делится).
Вы уверены,что алгоритм более быстрый?
zer0mail
2187 / 1870 / 187
Регистрация: 03.07.2012
Сообщений: 6,658
Записей в блоге: 1
11.03.2014, 22:11     Самый большой простой делитель числа #6
Я при решении олимпиадных задач писал и сравнивал алгоритмы поиска простых чисел (например, для задачи разложения числа на простые сомножители).
Новичок
11.03.2014, 22:20
  #7

Не по теме:

Цитата Сообщение от zer0mail Посмотреть сообщение
для задачи разложения числа на простые сомножители
Дело в том что, я решая эту задачу, использовал перебор до округленного корня квадратного: первый делитель который мы найдем данным перебором - точно простой. Кстати, умудрился здать,да еще и рекурсией решал.

ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,056
11.03.2014, 22:25     Самый большой простой делитель числа #8
Цитата Сообщение от zer0mail Посмотреть сообщение
Но ровно половиной - может
может
например 6 3 и 2 оба простые
это я накосячил
Цитата Сообщение от Новичок Посмотреть сообщение
По моему достаточно перебирать делители до округленного корня квадратного.
тоже правильно

но вот какой вопрос возник у меня
а если число само простое? например 11
может с конца начинать?
сначала на само себя
потом на половину( корень)?

Добавлено через 1 минуту
Цитата Сообщение от zer0mail Посмотреть сообщение
(и уменьшением X, если делится).
а уменьшение то зачем?
Новичок
Модератор
 Аватар для Новичок
1141 / 712 / 148
Регистрация: 17.07.2012
Сообщений: 4,044
Записей в блоге: 1
Завершенные тесты: 2
11.03.2014, 22:27     Самый большой простой делитель числа #9
Цитата Сообщение от ValeryS Посмотреть сообщение
а если число само простое?
Перебирая делители от 2 до округленного корня квадратного этого числа можно сразу узнать простое ли число. Если число простое - делителей не найдет. Если составное - хоть один делитель найдет.
zer0mail
2187 / 1870 / 187
Регистрация: 03.07.2012
Сообщений: 6,658
Записей в блоге: 1
11.03.2014, 22:43     Самый большой простой делитель числа #10
Перебираем простые p, пока p*p<=X. Если X делится на простое m, то "новый" X=X/m(пока делится).
Чем больше у X делителеЙ, тем ниже граница для p.

Добавлено через 11 минут
Цитата Сообщение от ValeryS Посмотреть сообщение
а если число само простое? например 11
может с конца начинать?
сначала на само себя
На себя любое число поделится. Я не знаю другого способа определения простоты X, кроме как поделить его "снизу" на все простые до корень(X). Замечание: "снизу" до корня ближе, чем "сверху"

Общий подход: Создается и заполняется снизу массив простых чисел, причем при заполнении нового элемента используются ранее заполненные. В процессе заполнения выполняются действия, связанные с решаемой задачей.
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,056
11.03.2014, 23:45     Самый большой простой делитель числа #11
Цитата Сообщение от zer0mail Посмотреть сообщение
Замечание: "снизу" до корня ближе, чем "сверху"
Цитата Сообщение от Новичок Посмотреть сообщение
Перебирая делители от 2 до округленного корня квадратного этого числа можно сразу узнать простое ли число.
ну и
делили делили не делится
давай делить на себя

по шагам что сверху что снизу одинаково

теперь возьмем другой вариант число 121, например
снизу
на 2 не делится
на 3 не делится
на 5 не делится
на 7 не делится
на 11 делится, дальше можно не продолжать ибо корень
итого 5 итераций

теперь сверху
121 делится
11, корень делится выходим
итого 2 итерации

в самом пиковом случае когда число простое будет столько же итераций что сверху что снизу
в остальных случаях меньше, ну если не брать маленькие числа типа 6 8 там тоже равно будет

Добавлено через 7 минут
Цитата Сообщение от Новичок Посмотреть сообщение
По моему достаточно перебирать делители до округленного корня квадратного.
сейчас понял не получается
все таки до половины
число 14
корень 3.74 ну округлим до 4
а наибольший то простой делитель 7
до корня это если число на простоту проверять

Добавлено через 4 минуты
может вилкой попробовать, вот тогда корень и пригодится
например 45
делим на 2 не делится
делим на 3 делится второе число 15, не простое идем дальше
делим на 5 второе число 7, дальше можно не искать
ну это так мысли вслух, реализовывать не хочется
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
12.03.2014, 00:13     Самый большой простой делитель числа #12
C++
1
2
3
4
5
6
7
8
9
10
11
12
int del = 2, toto = (int)sqrt(n)+1;
while(del <= toto)
**if(n%del == 0)
***{
****max = del;
****n /= del;
***}
**else
***++del;
 
if(n>1)
*max = maximum(max, n)
Добавлено через 18 минут
Цитата Сообщение от Dani Посмотреть сообщение
if(n>1)
*max = maximum(max, n)
Хотя, вместо этого можно просто написать
if(n>1) max = n;
Retyrn0
45 / 45 / 3
Регистрация: 24.06.2013
Сообщений: 675
Завершенные тесты: 1
12.03.2014, 02:29     Самый большой простой делитель числа #13
Цитата Сообщение от ValeryS Посмотреть сообщение
цикл можно уменьшить
Если ещё и стремиться к оптимизации, то правильнее будет воспользоваться инверсным циклом,
ибо
Цитата Сообщение от Outmee Посмотреть сообщение
Самый большой
C++
1
2
3
4
5
for (int i = numb/2; i >= 3; i-=2)
{
//...
//Если число удовлетворяет критерию поиска, break;
}
zer0mail
2187 / 1870 / 187
Регистрация: 03.07.2012
Сообщений: 6,658
Записей в блоге: 1
12.03.2014, 08:01     Самый большой простой делитель числа #14
Ни фига себе оптимизация! Если число ~1012, то "до корня надо" ~5*105циклов, а до n/2 надо ~2*1011 (в пол-миллиона раз больше)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.03.2014, 10:11     Самый большой простой делитель числа
Еще ссылки по теме:

C++ Найти второй самый большой элемент массива и второй самый маленький элемент массива
Найти самый большой элемент матрицы по модулю и его индекс C++
Наименьший простой делитель C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Байт
 Аватар для Байт
13988 / 8819 / 1230
Регистрация: 24.12.2010
Сообщений: 15,975
12.03.2014, 10:11     Самый большой простой делитель числа #15
Не претендуя на оптимальность
C++
1
2
3
4
5
6
7
for(M=1, i=2; N>1; i++) {
  while(N%i==0) {
    M = i;
    N /= i;
  }
}
cout<< M;
Yandex
Объявления
12.03.2014, 10:11     Самый большой простой делитель числа
Ответ Создать тему
Опции темы

Текущее время: 10:49. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru