Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
Outmee
2 / 2 / 1
Регистрация: 26.01.2014
Сообщений: 59
Завершенные тесты: 1
#1

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

11.03.2014, 20:37. Просмотров 2158. Ответов 14
Метки нет (Все метки)

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");
}
как я только не жонглировал с числами, все равно пишет не то.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.03.2014, 20:37
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Самый большой простой делитель числа (C++):

Найти максимальный простой делитель числа
#include &lt;iostream&gt; using namespace std; int main () {int i,j; int a; ...

Как переставить местами самый маленький и самый большой элементы массива?
1. Переставить местами маленький и самый большой элементы массива

Самый самый самый простой пример рекурсии
приведите самый прост пример рекурсии)))void main(int k) { int n=10; k=n;...

Самый простой способ конвертации целого числа в строку
всем привет! подскажите самый простой способ конвертации int to string (или...

самый, самый большой ))
народ че делать unsigned long long int - оказался недостаточен есть тип...

Самый большой целый тип данных
Есть задача,в которой,по условию, на вход может подаваться целое число N...

14
zer0mail
2451 / 2085 / 216
Регистрация: 03.07.2012
Сообщений: 7,566
Записей в блоге: 1
11.03.2014, 21:16 #2
Надо не жонглировать числами, а придумать алгоритм и реализовать его.
Опиши словами алгоритм, который хотел запрограммировать.
0
ValeryS
Модератор
7134 / 5402 / 669
Регистрация: 14.02.2011
Сообщений: 18,225
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 это тоже простое число
0
zer0mail
2451 / 2085 / 216
Регистрация: 03.07.2012
Сообщений: 7,566
Записей в блоге: 1
11.03.2014, 21:51 #4
Цитата Сообщение от ValeryS Посмотреть сообщение
делитель не может быть больше половины
Но ровно половиной - может . Правильный алгоритм - быстрый поиск простых чисел с одновременной проверкой, делится ли X на новое простое число (и уменьшением X, если делится).
0
Новичок
Модератор
1482 / 949 / 457
Регистрация: 17.07.2012
Сообщений: 4,888
Завершенные тесты: 3
11.03.2014, 22:04 #5
По моему достаточно перебирать делители до округленного корня квадратного.

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

Не по теме:

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

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

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

Добавлено через 1 минуту
Цитата Сообщение от zer0mail Посмотреть сообщение
(и уменьшением X, если делится).
а уменьшение то зачем?
0
Новичок
Модератор
1482 / 949 / 457
Регистрация: 17.07.2012
Сообщений: 4,888
Завершенные тесты: 3
11.03.2014, 22:27 #9
Цитата Сообщение от ValeryS Посмотреть сообщение
а если число само простое?
Перебирая делители от 2 до округленного корня квадратного этого числа можно сразу узнать простое ли число. Если число простое - делителей не найдет. Если составное - хоть один делитель найдет.
0
zer0mail
2451 / 2085 / 216
Регистрация: 03.07.2012
Сообщений: 7,566
Записей в блоге: 1
11.03.2014, 22:43 #10
Перебираем простые p, пока p*p<=X. Если X делится на простое m, то "новый" X=X/m(пока делится).
Чем больше у X делителеЙ, тем ниже граница для p.

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

Общий подход: Создается и заполняется снизу массив простых чисел, причем при заполнении нового элемента используются ранее заполненные. В процессе заполнения выполняются действия, связанные с решаемой задачей.
0
ValeryS
Модератор
7134 / 5402 / 669
Регистрация: 14.02.2011
Сообщений: 18,225
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, дальше можно не искать
ну это так мысли вслух, реализовывать не хочется
0
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 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;
0
Retyrn0
45 / 45 / 5
Регистрация: 24.06.2013
Сообщений: 677
Завершенные тесты: 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;
}
0
zer0mail
2451 / 2085 / 216
Регистрация: 03.07.2012
Сообщений: 7,566
Записей в блоге: 1
12.03.2014, 08:01 #14
Ни фига себе оптимизация! Если число ~1012, то "до корня надо" ~5*105циклов, а до n/2 надо ~2*1011 (в пол-миллиона раз больше)
0
Байт
Эксперт C
17771 / 11796 / 2450
Регистрация: 24.12.2010
Сообщений: 23,718
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;
0
12.03.2014, 10:11
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.03.2014, 10:11
Привет! Вот еще темы с решениями:

Найти самый большой элемент Массива
Помогите с заданием не как не могу сообразить С помощью датчика случайных...

Наименьший простой делитель
Найдите наименьший простой делитель натурального числа.

Найти самый большой положительный элемент заданного массива
надо составить программу который определить самого большого положительного...

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


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru