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

Получить все простые делители заданного натурального числа

23.12.2016, 10:40. Просмотров 1429. Ответов 20
Метки нет (Все метки)

Бьюсь с этой задачей уже несколько часов.
Выдает сбой в вычислениях, и я не могу понять почему.

За проверку брал число 1463. Раскладывается на простые делители 7, 11, 19. И программа выводит эти числа! А потом еще. Но почему? SOS!

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
#include <iostream>
#include <math.h>
using namespace std;
void main()
{
    setlocale (LC_ALL, "rus");
    int n, i, a;
    cout << "введите любое натуральное число: \n";
    cin >> n;
 
    for (i=2; i<=n; i++)
    { 
        if ( n % i != 0 )  // если остаток от деления равен 0, то i - делитель числа n
            {continue;}
        for  (a=2; a<=(i-1); a++)
            {   if ( i % a == 0 ) 
                { continue; }
                cout << i << endl; 
                break;
            }
            
        }
    
   system ("pause");
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.12.2016, 10:40
Ответы с готовыми решениями:

Найти все простые делители заданного натурального числа
Дано натуральное число n. Получить все простые делители этого числа.

Получить все простые делители натурального числа
2. Дано натуральное число n. Получить все простые делители этого числа.

Циклические алгоритмы: вывести на экран все простые делители заданного натурального числа
Вывести на экран все простые делители заданного натурального числа

Получить все простые делители заданного числа
Дано натуральное число n. Получить все простые делители этого числа. (нужно...

Найти все простые положительные делители данного натурального числа
Help!: Дано натуральное число N. Найти все его простые положительные делители....

20
afront
1050 / 997 / 752
Регистрация: 29.02.2016
Сообщений: 3,187
23.12.2016, 11:17 2
C++
1
2
3
4
5
     n=1463;
    for (i=2; i<=n-1; i++)
        if ( n % i  == 0 )  // если остаток от деления равен 0, то i - делитель числа n
               cout << i << " "; 
    cout << endl;
Добавлено через 4 минуты
Найти все простые положительные делители данного натурального числа
0
gullsoup
0 / 0 / 0
Регистрация: 23.12.2016
Сообщений: 7
23.12.2016, 11:24  [ТС] 3
afront, с Вами все в порядке?
0
afront
1050 / 997 / 752
Регистрация: 29.02.2016
Сообщений: 3,187
23.12.2016, 11:51 4
C++
1
2
3
4
5
   n=1463;
    for (i=2; i<=sqrt(n); i++)
        if ( n % i  == 0 )  // если остаток от деления равен 0, то i - делитель числа n
            cout << i << " "; 
    cout << endl;
0
gullsoup
0 / 0 / 0
Регистрация: 23.12.2016
Сообщений: 7
23.12.2016, 11:59  [ТС] 5
afront, не объясните словами, почему нужно искать именно до квадратного корня из заданного числа?
0
Mr.X
Эксперт С++
3179 / 1706 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
23.12.2016, 12:15 6
Цитата Сообщение от gullsoup Посмотреть сообщение
afront, не объясните словами
Да-да, и пусть объяснит, почему его выводимые делители не так просты, как хотелось бы, например, если число 1024 протестировать!

Добавлено через 3 минуты
Ну, недавно уже была эта задача.
0
gullsoup
0 / 0 / 0
Регистрация: 23.12.2016
Сообщений: 7
23.12.2016, 12:31  [ТС] 7
Mr.X, там с функциями и совершенно другой алгоритм. Хотелось бы уже свой вариант добить, где в нем косяки. Упорно их не вижу из-за нехватки то ли знаний, то ли опыта.

И почему мой вариант для 1024 вообще не работает?
0
Mr.X
Эксперт С++
3179 / 1706 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
23.12.2016, 12:48 8
Лучший ответ Сообщение было отмечено MrGluck как решение

Решение

Цитата Сообщение от gullsoup Посмотреть сообщение
там с функциями
А куда ж без них-то! Никогда не понимал людей, которые ссыпают весь код в main в сыром виде.
Это вас в школе учат таким безобразиям?!
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
39
40
41
42
#include <iostream>
///////////////////////////////////////////////////////////////////////////////
void    print_prime_factors( int    n )
{
    for ( int i = 2; i*i <= n; ++i )
    {
        if  (
                n % i   ==  0
            )
        {
            std::cout   << i
                        << ' ';
 
            while( n % i    ==  0 )
            {
                n   /=  i;
            }
        }//if
    }
 
    if( n != 1 )
    {
        std::cout   <<  n;
    }
 
    std::cout   <<  std::endl
                <<  "finish"
                <<  std::endl
                <<  std::endl;
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    for(;;)
    {
        int     n{};
        std::cout   <<  "n = ";
        std::cin    >>  n;
 
        print_prime_factors(n);
    }//for
}
1
MrGluck
Модератор
Эксперт CЭксперт С++
8086 / 4939 / 1431
Регистрация: 29.11.2010
Сообщений: 13,395
23.12.2016, 12:58 9
Цитата Сообщение от gullsoup Посмотреть сообщение
там с функциями и совершенно другой алгоритм.
main - тоже функция, если что

Добавлено через 5 минут
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cmath>
#include <iostream>
 
bool IsPrime(const int n)
{
    for (int i = 2; i <= sqrt(n); i++)
        if (n % i == 0)
            return false;
    return n > 1;
}
 
void PrintPrimeDivisors(const int n)
{
    for (int i = 2; i <= sqrt(n); i++)
        if (n % i == 0 && IsPrime(i))
            std::cout << i << " ";
}
 
int main()
{
    PrintPrimeDivisors(1463);
}
Добавлено через 3 минуты
Но если посмотреть на эту задачку математически, то можно даже упростить:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
 
int NOD(int a, int b)
{
    while (a && b)
        a > b ? a %= b : b %= a;
    return a | b;
}
 
void PrintPrimeDivisors(const int n)
{
    for (int i = 2; i*i <= n; i++)
        if (NOD(n, i) == i)
            std::cout << i << " ";
}
 
int main()
{
    PrintPrimeDivisors(1463);
}
0
gullsoup
0 / 0 / 0
Регистрация: 23.12.2016
Сообщений: 7
23.12.2016, 13:04  [ТС] 10
Mr.X, в институте требуют так, как учили. Предполагается, что эту работу должны были сделать без знания функций, только циклы.
Прошу Вас, объясните мне словами принцип работы!
0
MrGluck
Модератор
Эксперт CЭксперт С++
8086 / 4939 / 1431
Регистрация: 29.11.2010
Сообщений: 13,395
23.12.2016, 13:10 11
Лучший ответ Сообщение было отмечено gullsoup как решение

Решение

Думаю так, школьным способом, даже быстрее получится:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
 
void PrintPrimeDivisors(int n)
{
    while (n > 1)
        for (int i = 2; i <= n; i++)
            if (n % i == 0)
            {
                std::cout << i << " ";
                n /= i;
                break;
            }
}
Надо только проверять на дубли.
1
Mr.X
Эксперт С++
3179 / 1706 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
23.12.2016, 13:15 12
Цитата Сообщение от MrGluck Посмотреть сообщение
Но если посмотреть на эту задачку математически
Да, на этой задаче уже немало наших полегло!
Цитата Сообщение от Mr.X Посмотреть сообщение
и пусть объяснит, почему его выводимые делители не так просты, как хотелось бы, например, если число 1024 протестировать!
1
MrGluck
Модератор
Эксперт CЭксперт С++
8086 / 4939 / 1431
Регистрация: 29.11.2010
Сообщений: 13,395
23.12.2016, 13:17 13
Как то так:
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>
#include <unordered_set>
 
bool IsPrime(const int n)
{
    for (int i = 2; i*i <= n; i++)
        if (n % i == 0)
            return false;
    return n > 1;
}
 
std::unordered_set<int> GetPrimeDivisors(int n)
{
    static std::unordered_set<int> us;
    for (int i = 2; i <= n; i++)
        if (n % i == 0)
        {
            if (IsPrime(i))
                us.insert(i);
            n /= i;
            if (n != 1)
               GetPrimeDivisors(n);
        }
    return us;
}
 
int main()
{
    for (const auto x : GetPrimeDivisors(1024))
        std::cout << x << " ";
}
0
Mr.X
Эксперт С++
3179 / 1706 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
23.12.2016, 13:17 14
Цитата Сообщение от gullsoup Посмотреть сообщение
Прошу Вас, объясните мне словами принцип работы!
А чего тут объяснять, находим наименьший делитель и делим на него, и так пока они есть.
0
_Ivana
3233 / 1861 / 234
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 5
23.12.2016, 13:20 15
Цитата Сообщение от MrGluck Посмотреть сообщение
Как то так:
Простите, но это АдЪ и Израиль. Есть же нормальный алгоритм на порядок проще и быстрее.
0
MrGluck
Модератор
Эксперт CЭксперт С++
8086 / 4939 / 1431
Регистрация: 29.11.2010
Сообщений: 13,395
23.12.2016, 13:29 16
Цитата Сообщение от _Ivana Посмотреть сообщение
Есть же нормальный алгоритм на порядок проще и быстрее.
Возможно, я как раз пытаюсь оптимизировать вариант нахождения "в лоб".

Мой вариант - нахождение делителей "школьным способом" с проверкой чисел на простоту.

Добавлено через 5 минут
Хотя у Mr.X написан тот же вариант, но лучше. Действительно, можно сразу убрать все текущие делители в цикле.
0
_Ivana
3233 / 1861 / 234
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 5
23.12.2016, 13:29 17
И это еще не оптимизирован цикл - надо как минимум тривиально выкинуть проверку всех четных после двойки, а еще лучше - итерироваться по заранее предрассчитанному списку простых.
C++
1
2
3
4
5
6
7
8
typedef unsigned long long int ull;
 
void f(ull n) {
    for (int i=2; i*i<=n; i++) while (n%i==0) { cout<<i<<' '; n /= i; }
    if (n>1) cout<<n<<' ';
}
 
int main() { for(ull n=1000; n<=1024; n++) { cout<<n<<": "; f(n); cout<<'\n';} }
1000: 2 2 2 5 5 5
1001: 7 11 13
1002: 2 3 167
1003: 17 59
1004: 2 2 251
1005: 3 5 67
1006: 2 503
1007: 19 53
1008: 2 2 2 2 3 3 7
1009: 1009
1010: 2 5 101
1011: 3 337
1012: 2 2 11 23
1013: 1013
1014: 2 3 13 13
1015: 5 7 29
1016: 2 2 2 127
1017: 3 3 113
1018: 2 509
1019: 1019
1020: 2 2 3 5 17
1021: 1021
1022: 2 7 73
1023: 3 11 31
1024: 2 2 2 2 2 2 2 2 2 2
1
MrGluck
Модератор
Эксперт CЭксперт С++
8086 / 4939 / 1431
Регистрация: 29.11.2010
Сообщений: 13,395
23.12.2016, 13:32 18
_Ivana, да я уже заметил, что можно просто убрать дубли, поделив в цикле на текущий делитель. Этот вариант уже написан у Mr.X.

Добавлено через 48 секунд
Заявляю на всеуслышание: код с unordered_set - говно.
0
gullsoup
0 / 0 / 0
Регистрация: 23.12.2016
Сообщений: 7
23.12.2016, 13:53  [ТС] 19
Дорогие, очень благодарен вам за отзывчивость, но, боюсь, все это мне не поможет.
Ваша помощь мне нужна в объяснении, а не в коде.

От меня требовалось придумать алгоритм. Я придумал: проверяем является ли число делителем, если нет, проверяем новое, если да, проверяем его на простоту, выбрав как условие присутствие остатка при делении.

Но по какой-то причине он не работает. От вас я и прошу помочь найти эту ошибку, или указать, почему этот шаг моего алгоритма неправильный, а не писать новый! :с
0
Mr.X
Эксперт С++
3179 / 1706 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
23.12.2016, 14:05 20
Цитата Сообщение от gullsoup Посмотреть сообщение
проверяем является ли число делителем, если нет, проверяем новое, если да, проверяем его на простоту
Ну, если делитель наименьший, то его не надо проверять на простоту, так как если бы он был составной, то наименьшим был бы его делитель.
1
23.12.2016, 14:05
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.12.2016, 14:05

Вывести все делители заданного натурального числа с++
Вывести все делители заданного натурального числа

Получить все простые делители числа
Дано натуральное число n. Получить все простые делители этого числа. Помогите...

Получить все простые делители числа
Здравствуйте, помогите, пожалуйста. Дано целое число n. Получить все простые...


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

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

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