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

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

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

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

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

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

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

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

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

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

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
3233 / 1861 / 235
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 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
3233 / 1861 / 235
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 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
3233 / 1861 / 235
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 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
3233 / 1861 / 235
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 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
3233 / 1861 / 235
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 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; void main() {...

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

Для каждого из некоторого количества натуральных чисел найти простой делитель наибольшой кратности
для каждого из некоторого количества натуральных чисел найти простой делитель...

Создать одномерный массив, найти наименьший элемент 3-го столбца, поменять местами наименьший элемент элементы
Дана матрица А(5,3) 1 Создать новый одномерный массив,каждый элемент которого...


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

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

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