Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.63/8: Рейтинг темы: голосов - 8, средняя оценка - 4.63
kos04
0 / 0 / 0
Регистрация: 10.10.2014
Сообщений: 12
1

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

10.10.2014, 21:34. Просмотров 1581. Ответов 12
Метки нет (Все метки)

Найдите наименьший простой делитель натурального числа.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.10.2014, 21:34
Ответы с готовыми решениями:

Наименьший общий делитель. Алгоритм Евклида.
Наименьший общий делитель. Алгоритм Евклида. int protect(int maxnum,int...

Найти наименьший натуральный делитель числа
Дано целое число, не меньшее 2. Выведите его наименьший натуральный делитель,...

Наименьший общий делитель двух чисел
Определите функцию , которая возвращает НАИМЕНЬШИЙ общий делитель а и b.

Рекурсия. Наименьший общий делитель по формулам Евклида
Подскажите как выполнить рекурсию. прога работает, но без рекурсии. задание...

Найти наименьший общий делитель в произвольном массиве
Товарищи, доброго времени суток! Никак не могу совладать с алгоритмистикой...

12
D_in_practice
331 / 331 / 331
Регистрация: 02.10.2014
Сообщений: 666
13.10.2014, 15:22 2
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
30
31
#include <iostream>
 
using namespace std;
 
int main(){
 
    int n;
            
    cout << "Ââåäèòå n = ";
    cin >> n;
    
    int simple = 0;
    
    for (int i = 2; i < n; ++i)
        if (n % i == 0){
            simple = i;
            break;
        }   
    
    if (simple == 0)
        simple = n; 
    
    if (n > 1)
        cout << "simple = " << simple << endl;
    else if (n == 0)
        cout << "simple = " << 2 << endl;
    else
        cout << "Г“ Г¤Г*Г*Г*îãî Г·ГЁГ±Г«Г* Г*ГҐ ìîæåò áûòü ïðîñòîãî äåëèòåëÿ" << endl;
 
    return 0;
}
1
_Ivana
3236 / 1863 / 235
Регистрация: 01.03.2013
Сообщений: 5,108
Записей в блоге: 5
13.10.2014, 15:28 3
1.

Добавлено через 3 минуты
ЗЫ а нет, я лохЪ - по последним данным разведки 1 не считается простым числом
0
D_in_practice
331 / 331 / 331
Регистрация: 02.10.2014
Сообщений: 666
13.10.2014, 15:31 4
'0' не всегда является натуральным числом
например в математике.
для языка С++ думаю это натуральное число, потому что с него начинается счет некоторых массивов
0
_Ivana
3236 / 1863 / 235
Регистрация: 01.03.2013
Сообщений: 5,108
Записей в блоге: 5
13.10.2014, 15:58 5
Насколько я не знаю, 0 не входит в множество натуральных чисел, но входит в "расширенное" множество натуральных чисел. Иначе оно не будет моноидом по сложению Это значит, что на множестве должна быть определена ассоциативная бинарная операция и в множестве должен существовать элемент "нейтральный" относительно этой операции.

Но в данном случае ситуация другая, не про ноль. Единицу не признают простым числом. Типа как параллелограмм не признают трапецией.
0
Boleon
Guardian of Asgaard
373 / 316 / 197
Регистрация: 11.11.2013
Сообщений: 1,046
Завершенные тесты: 1
13.10.2014, 16:22 6
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
30
31
32
33
34
35
36
37
38
#include <iostream>
 
using namespace std;
 
int simple(int n) {
    for ( int i = 2; i * i <= n; i++ ) {
        if ( n % i == 0 ) {
            return 0;
        }
    }
    return 1;
}
int result(int n) {
    for ( int i = 2; i <= n; i++ ) {
        if ( simple(i) && n % i == 0 ) {
            return i;
        }
    }
    return 0;
}
 
int main() {
    int number;
    
    cin >> number;
 
    if ( number < 0 ) {
        number *= -1;
    }
    
    if ( result(number) ) {
        cout << result(number) << endl;
    } else {
        cout << "There are not simple dividers." << endl;
    }
    
    return 0;
}
0
_Ivana
3236 / 1863 / 235
Регистрация: 01.03.2013
Сообщений: 5,108
Записей в блоге: 5
13.10.2014, 16:31 7
Darkrduk, ужас, адЪ и Израиль!
1. Нафига (!) проверять число на простоту и тратить на это силы процессора? У вас никогда не поделится на 6, если
предварительно не поделится на 2 и 3!
2. Нафига бежать до n-1? Если у вас не поделилось на 2, то не поделится и на n/2! Тем более на n-1! Бежать до квадратного корня.
3. Нафига проверять заведомо не простые делители? Хотя, это уже вещи второго порядка...
1
D_in_practice
331 / 331 / 331
Регистрация: 02.10.2014
Сообщений: 666
13.10.2014, 16:39 8
Учтем предыдущие замечания.
Немного улучшим код:
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
30
31
#include <iostream>
 
using namespace std;
 
int main(){
 
    int n;          
    do{
        cout << "Ââåäèòå n = ";
        cin >> n;
    }while(n < 0);
        
    int simple = 0; 
    for (int i = 2; i * i < n; ++i)
        if (n % i == 0){
            simple = i;
            break;
        }   
    
    if (simple == 0)
        simple = n; 
    
    if (n > 1)
        cout << "simple = " << simple << endl;
    else if (n == 0)
        cout << "simple = " << 2 << endl;
    else
        cout << "Г“ Г¤Г*Г*Г*îãî Г·ГЁГ±Г«Г* Г*ГҐ ìîæåò áûòü ïðîñòîãî äåëèòåëÿ" << endl;
 
    return 0;
}
0
_Ivana
3236 / 1863 / 235
Регистрация: 01.03.2013
Сообщений: 5,108
Записей в блоге: 5
13.10.2014, 16:42 9
АдЪ ушел, Израиль остался. Допустим, у вас нечетное число. Вы проверили, на 2 оно не делится.
1. Нафига ++i и мучать проверкой на четные делители?
2. По-хорошему, надо по простым бежать.

ЗЫ и если задача именно в поиске первого простого делителя, а не полной факторизации числа, то можно не говорить о некоторой оптимизации, которая сильно помогает в случае факторизации.
0
D_in_practice
331 / 331 / 331
Регистрация: 02.10.2014
Сообщений: 666
13.10.2014, 16:53 10
Цитата Сообщение от _Ivana Посмотреть сообщение
АдЪ ушел, Израиль остался. Допустим, у вас нечетное число. Вы проверили, на 2 оно не делится.
1. Нафига ++i и мучать проверкой на четные делители?
2. По-хорошему, надо по простым бежать.
да, с применением массива простых чисел быстрее, но здесь это лишнее
0
Boleon
Guardian of Asgaard
373 / 316 / 197
Регистрация: 11.11.2013
Сообщений: 1,046
Завершенные тесты: 1
13.10.2014, 18:11 11
Цитата Сообщение от _Ivana Посмотреть сообщение
Нафига (!) проверять число на простоту и тратить на это силы процессора?
Дык ведь:
Цитата Сообщение от kos04 Посмотреть сообщение
Найдите наименьший простой делитель
Добавлено через 46 минут
П.С.
понял свой "пролёт"
0
sleepy_cat
2 / 2 / 6
Регистрация: 29.08.2014
Сообщений: 16
13.10.2014, 18:23 12
Можно с помощью решета Эратосфена искать простые числа меньшие n и для каждого простого проверять, делит ли оно n.
0
_Ivana
3236 / 1863 / 235
Регистрация: 01.03.2013
Сообщений: 5,108
Записей в блоге: 5
13.10.2014, 18:30 13
Вот это уже больше похоже на правду. Но, как уже отметили, скорее всего ТС нужен просто неоптимизированный быдлокод чтобы сдать лабу и забыть программирование как страшный сон. Но не для него ведь распинаюсь - а для советчиков, которые вроде как язык немного знают, а пишут адЪ и Израиль - с них спрос больше и подход другой. "Я так думаю" (С) (жаль тут нет того усатого смайлика в кепке под эту фразу )
0
13.10.2014, 18:30
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.10.2014, 18:30

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

Самый большой простой делитель числа
#include &lt;iostream&gt; using namespace std; void main() {...

Найти наименьший делитель числа Х, который в двенадцатеричной системе состоит из одинаковых цифр
Всем привет! Вот на учебе задали задачу, но никак не могу решить ее. Как...


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

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

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