Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

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

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

11.03.2014, 20:37. Просмотров 1770. Ответов 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++):

Найти максимальный простой делитель числа - C++
#include &lt;iostream&gt; using namespace std; int main () {int i,j; int a; double x,y,max; cout &lt;&lt; (&quot;vvedi x&quot;); cin &gt;&gt; x ; ...

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

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

Самый простой способ конвертации целого числа в строку - C++
всем привет! подскажите самый простой способ конвертации int to string (или string to int), без разницы, какой проще. знаю о itoa, но...

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

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

14
zer0mail
2378 / 2009 / 200
Регистрация: 03.07.2012
Сообщений: 7,248
Записей в блоге: 1
11.03.2014, 21:16 #2
Надо не жонглировать числами, а придумать алгоритм и реализовать его.
Опиши словами алгоритм, который хотел запрограммировать.
0
ValeryS
Модератор
6729 / 5138 / 484
Регистрация: 14.02.2011
Сообщений: 17,233
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
2378 / 2009 / 200
Регистрация: 03.07.2012
Сообщений: 7,248
Записей в блоге: 1
11.03.2014, 21:51 #4
Цитата Сообщение от ValeryS Посмотреть сообщение
делитель не может быть больше половины
Но ровно половиной - может . Правильный алгоритм - быстрый поиск простых чисел с одновременной проверкой, делится ли X на новое простое число (и уменьшением X, если делится).
0
Новичок
Модератор
1279 / 826 / 190
Регистрация: 17.07.2012
Сообщений: 4,353
Записей в блоге: 1
Завершенные тесты: 3
11.03.2014, 22:04 #5
По моему достаточно перебирать делители до округленного корня квадратного.

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

Не по теме:

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

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

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

Добавлено через 1 минуту
Цитата Сообщение от zer0mail Посмотреть сообщение
(и уменьшением X, если делится).
а уменьшение то зачем?
0
Новичок
Модератор
1279 / 826 / 190
Регистрация: 17.07.2012
Сообщений: 4,353
Записей в блоге: 1
Завершенные тесты: 3
11.03.2014, 22:27 #9
Цитата Сообщение от ValeryS Посмотреть сообщение
а если число само простое?
Перебирая делители от 2 до округленного корня квадратного этого числа можно сразу узнать простое ли число. Если число простое - делителей не найдет. Если составное - хоть один делитель найдет.
0
zer0mail
2378 / 2009 / 200
Регистрация: 03.07.2012
Сообщений: 7,248
Записей в блоге: 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
Модератор
6729 / 5138 / 484
Регистрация: 14.02.2011
Сообщений: 17,233
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 / 57
Регистрация: 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 / 3
Регистрация: 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
2378 / 2009 / 200
Регистрация: 03.07.2012
Сообщений: 7,248
Записей в блоге: 1
12.03.2014, 08:01 #14
Ни фига себе оптимизация! Если число ~1012, то "до корня надо" ~5*105циклов, а до n/2 надо ~2*1011 (в пол-миллиона раз больше)
0
Байт
Нарушитель
Эксперт C
16653 / 10930 / 1674
Регистрация: 24.12.2010
Сообщений: 21,298
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
Привет! Вот еще темы с ответами:

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

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

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

Найти второй самый большой элемент массива и второй самый маленький элемент массива - C++
Помогите пожалуйста: Найти второй самый большой элемент массива и второй самый маленький элемент массива.


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

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

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