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

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

Войти
Регистрация
Восстановить пароль
 
kos04
0 / 0 / 0
Регистрация: 10.10.2014
Сообщений: 12
#1

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

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

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

Наименьший общий делитель. Алгоритм Евклида. - C++
Наименьший общий делитель. Алгоритм Евклида. int protect(int maxnum,int minnum); int _tmain(int &n, int &m); int nod (int n,...

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

Найти наименьший натуральный делитель числа - C++
Дано целое число, не меньшее 2. Выведите его наименьший натуральный делитель, отличный от 1. Формат входных данных Вводится целое...

Найти наименьший общий делитель в произвольном массиве - C++
Товарищи, доброго времени суток! Никак не могу совладать с алгоритмистикой данной задачи - вроде результат при некоторых значениях...

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

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

12
D_in_practice
331 / 331 / 159
Регистрация: 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
3185 / 1801 / 153
Регистрация: 01.03.2013
Сообщений: 5,030
Записей в блоге: 3
13.10.2014, 15:28 #3
1.

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

Но в данном случае ситуация другая, не про ноль. Единицу не признают простым числом. Типа как параллелограмм не признают трапецией.
0
Boleon
Guardian of Asgaard
372 / 315 / 106
Регистрация: 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
3185 / 1801 / 153
Регистрация: 01.03.2013
Сообщений: 5,030
Записей в блоге: 3
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 / 159
Регистрация: 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
3185 / 1801 / 153
Регистрация: 01.03.2013
Сообщений: 5,030
Записей в блоге: 3
13.10.2014, 16:42 #9
АдЪ ушел, Израиль остался. Допустим, у вас нечетное число. Вы проверили, на 2 оно не делится.
1. Нафига ++i и мучать проверкой на четные делители?
2. По-хорошему, надо по простым бежать.

ЗЫ и если задача именно в поиске первого простого делителя, а не полной факторизации числа, то можно не говорить о некоторой оптимизации, которая сильно помогает в случае факторизации.
0
D_in_practice
331 / 331 / 159
Регистрация: 02.10.2014
Сообщений: 666
13.10.2014, 16:53 #10
Цитата Сообщение от _Ivana Посмотреть сообщение
АдЪ ушел, Израиль остался. Допустим, у вас нечетное число. Вы проверили, на 2 оно не делится.
1. Нафига ++i и мучать проверкой на четные делители?
2. По-хорошему, надо по простым бежать.
да, с применением массива простых чисел быстрее, но здесь это лишнее
0
Boleon
Guardian of Asgaard
372 / 315 / 106
Регистрация: 11.11.2013
Сообщений: 1,046
Завершенные тесты: 1
13.10.2014, 18:11 #11
Цитата Сообщение от _Ivana Посмотреть сообщение
Нафига (!) проверять число на простоту и тратить на это силы процессора?
Дык ведь:
Цитата Сообщение от kos04 Посмотреть сообщение
Найдите наименьший простой делитель
Добавлено через 46 минут
П.С.
понял свой "пролёт"
0
sleepy_cat
2 / 2 / 1
Регистрация: 29.08.2014
Сообщений: 16
13.10.2014, 18:23 #12
Можно с помощью решета Эратосфена искать простые числа меньшие n и для каждого простого проверять, делит ли оно n.
0
_Ivana
3185 / 1801 / 153
Регистрация: 01.03.2013
Сообщений: 5,030
Записей в блоге: 3
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
Привет! Вот еще темы с ответами:

Самый большой простой делитель числа - C++
#include &lt;iostream&gt; using namespace std; void main() { setlocale(LC_ALL, &quot;Russian&quot;); cout &lt;&lt; &quot;Найдите самый большой...

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

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

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


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

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

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