Разложение на простые множители без рекурсии

@sergei60 · Регистрация: 10.06.2012

Студворк — интернет-сервис помощи студентам

Задача такая : Надо написать две функции get_all_divisorts и get_lowest_divisor. Функция main должна вызывать get_all_divisorts , которая в свою очередь имеет цикл :функция get_all_divisorts повторно вызывает get_lowest_divisor , каждый раз заменяя n результатом выражения n / i , где i это найденный делитель. Если возвращается само число n , значит , число простое и цикл должен быть прекращен

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
43
44
#include <math.h>
#include <iostream>
using namespace std;
void get_all_divisors(int n);
void get_lowest_divisors(int n);
int main () {
    int n;
    while (1){
    cout<<endl;
    cout<<"введем число(кроме 0) ";
    cin>>n;
    if( n==0)//если пользователь ввел 0 ,бесконечный цикл зав.
    break;
     get_all_divisors(n);
}   
    return 0;
}
void get_lowest_divisor(int n){
    int i;
    if(return (n)){
    cout<<i<<" i простое число";
}
    return 0;
}
    
    void get_all_divisors(int n){//void функция не возвращает зн.
               //но использует инструкцию return для выхода
               //из функции раньше времени.
         int i;
         double sqrt_of_n=sqrt((double)n);
         for( i=2; i<=sqrt_of_n ;i++)
            if(n%i==0){
                cout<<i<<",";
                
                get_lowest_divisor(n);
                             
    
        return ;
    }
        //если делитель не найден,число n -простое
        //напечатать число n и не выполнять дальнейшие вызовы.   
            
cout<<n;
}

Я понимаю,что ошибка где то в функции get_lowest_divisor

C++
1
2
3
4
5
    if(return (n)){
    cout<<i<<" i простое число";
}
    return 0;
}

@Krasiosoft · 22.07.2015, 18:13

Функция:

C++
1
void get_lowest_divisor(int n)

Возвращает void, а Вы пытаетесь вернуть число: return 0;

А что означает это:

C++
1
2
if(return (n)){
}

?

@rikimaru2013 · 22.07.2015, 18:25

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <math.h>
#include <iostream>
using namespace std;
void get_all_divisors( int n );
int get_next_divisor( int current_delitel, int number );
 
int main( )
{
    int n = 0;  // возьмите за правило инициализировать значение локальных переменных (далее полей) значениями по умолчанию - для int это 0 
    while(n == 0)
    {
        cout << endl;
        cout << "введем число(кроме 0) ";
        cin >> n;       
        if(n!=0)
            get_all_divisors( n );
    }
    return 0;
}
int get_next_divisor( int current_delitel,  int number ) 
// если метод должен вызываться несколько раз и возвращать верное значение, то ему должно приходить разные значения
// если метод возвращает значения у него тип возвращаемого значения не может быть void
 
{
    // алгоритм поиска следующего делителя
    // приходит нам предыдущий делитель, а мы ищем следующий или вовзращаем i == number, что кстате является его делителем)
    int i = current_delitel;    
    while(i < number)
    {
        if(number % i != 0)
            i++;        
        else
            break;      
    }
    return i;
}
 
void get_all_divisors( int n )
{
    int* arr = new int[188];
    int index = 0;
    int seach = 1;
    while(seach < n)
    {
        seach = get_next_divisor( seach, n );
        arr[index] = seach;
 
        index++;
        seach++;        
    }
 
 
    for(int i = 0; i < index; ++i)
    {
        cout << arr[i] << endl;
    }
 
}

@sergei60 · 23.07.2015, 07:51 **[ТС]**

rikimaru2013, Первоначальный код был таким .и надо его переделать в задании. Спасибо конечно за ответ ,но до arr я еще не дошел в книге .

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
#include <math.h>
#include <iostream>
using namespace std;
void get_divisors(int n);
int main () {
    int n;
    while (1){
    cout<<endl;
    cout<<"введем число(кроме 0) ";
    cin>>n;
    if( n==0)//если пользователь ввел 0 ,бесконечный цикл зав.
    break;
    get_divisors(n);
}   
    return 0;
}
    void get_divisors(int n){//void функция не возвращает зн.
               //но использует инструкцию return для выхода
               //из функции раньше времени.
         int i;
         double sqrt_of_n=sqrt((double)n);
         for( i=2; i<=sqrt_of_n ;i++)
            if(n%i==0){
                cout<<i<<",";
                
                get_divisors( n/i);//возвращает и печатает i 
                             
    
        return ;
    }
        //если делитель не найден,число n -простое
        //напечатать число n и не выполнять дальнейшие вызовы.   
            
cout<<n;
}

Добавлено через 11 часов 26 минут
Задача такая : Надо написать две функции get_all_divisorts и get_lowest_divisor. Функция main должна вызывать get_all_divisorts , которая в свою очередь имеет цикл :функция get_all_divisorts повторно вызывает get_lowest_divisor , каждый раз заменяя n результатом выражения n / i , где i это найденный делитель. Если возвращается само число n , значит , число простое и цикл должен быть прекращен

Добавлено через 1 час 8 минут
Смотрю на начальный код с рекурсией , где все делается в функции void get_divisors(int n). Ход мысли таков . Вместо рекурсии я должен вызвать новую функцию и передать ей полученную в цикле i. В этой новой функции , которую назвали get_lowest_divisor , я должен сделать действие n / i и if( n/i==0 ) , то вернуть назад это новое значение в функцию
void get_divisors(int n) , там оно добавится в список для выведения и все продолжится как в первом коде . Где ошибка в моих рассуждениях , если ошибки нет , то как реализовать это ?

Добавлено через 35 минут
Просьба спецов проверить ,правильное ли решение ?

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
#include <math.h>
#include <iostream>
using namespace std;
int get_lowest_divisor(int );
void get_divisors(int n);
int main () {
    int n;
    while (1){
    cout<<endl;
    cout<<"введем число(кроме 0) ";
    cin>>n;
    if( n==0)//если пользователь ввел 0 ,бесконечный цикл зав.
    break;
    get_divisors(n);
}   
    return 0;
}
    void get_divisors(int n){//void функция не возвращает зн.
               //но использует инструкцию return для выхода
               //из функции раньше времени.
         int i;
         double sqrt_of_n=sqrt((double)n);
         for( i=2; i<=sqrt_of_n ;i++)
            if(n%i==0){
            cout<<i<<",";
                get_lowest_divisor(n/i);
    return ;
    }
    cout<<n;
    }
int get_lowest_divisor(int n){
    int i;
    if(n/i==0)
    get_divisors(n);
    
}

@Krasiosoft · 23.07.2015, 19:26

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;
 
int get_lowest_divisor(int number){
    for(int i=2;i<=number;i++){
        if( number%i == 0) return i;
    }
    return 0;
}
 
void get_all_divisors(int number){
    for(int divisor=get_lowest_divisor( number );divisor;divisor=get_lowest_divisor( number/=divisor ) ){
        cout << divisor << " ";
    }
}
 
int main(){
 
    int n;
    do{
        cout << "Input number: ";
        cin >> n;
    }while(n == 0);
 
    get_all_divisors(n);
 
    return 0;
}

Что-то вроде этого нужно?

@sergei60 · 23.07.2015, 20:44 **[ТС]**

Krasiosoft, Спасибо большое (конечно лучше бы самому) ,но... Неясен длинный цикл ,пытаюсь разобраться.

@Krasiosoft · 23.07.2015, 21:01

Если вы про:

C++ (Qt)
1
for(int divisor=get_lowest_divisor( number );divisor;divisor=get_lowest_divisor( number/=divisor ) )

То тут:

Инициализация: int divisor=get_lowest_divisor( number ), т.е. берем первый делитель от оригинального числа
Условие: divisor, т.е. пока divisor не равен 0
Изменения значений на следующем шаге: divisor=get_lowest_divisor( number/=divisor ), т.е. делим число на делитель и передаем результат этого в get_lowest_divisor

@sergei60 · 24.07.2015, 17:30 **[ТС]**

Krasiosoft, Впервоначальном коде у меня есть строчка double sqrt_of_n=sqrt((double)n); то есть в цикле я нахожу простое число из корня ,для этого используется математическая функция sqrt и в цикле for( i=2; i<=sqrt_of_n ;i++). Пытаясь подставить корень в окончательный код ,программа перестает правильно работать . Она обрабатывает не все значения. Что я делаю не так ? Вот причесанный окончательный код.

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
#include <iostream>
 #include <cmath>
using namespace std;
 
int get_lowest_divisor(int n){
   double sqrt_of_n=sqrt((double)n);
         for( int i=2; i<=sqrt_of_n ;i++){
        if( n%i == 0) return i;
    }
    return 0;
}
 
void get_all_divisors(int n){
    for(int i=get_lowest_divisor(n);i;i=get_lowest_divisor(n=n/i)){
        cout << i << " ";
    }
}
 //инициализация: int i=get_lowest_divisor( n );
 //берем первый делитель от оригинального числа
 //Условие: i, т.е.пока i не равно 0
 //изменение значения на след. шаге  i=get_lowest_divisor( n/=i )
 //т.е. делим число на делитель и передаем результат этого
 //  в функцию get_lowest_divisor
int main () {
    int n;
    while (1){
    cout<<endl;
    cout<<"введем число(кроме 0) ";
    cin>>n;
    if( n==0)//если пользователь ввел 0 ,бесконечный цикл зав.
    break;
    get_all_divisors(n);
}
    return 0;
}

@Krasiosoft · 24.07.2015, 18:26

Тогда будет так:

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
#include <iostream>
#include <cmath>
 
using namespace std;
 
int get_lowest_divisor(int n){
    double sqrt_of_n = sqrt((double)n);
    for(int i=2; i<=sqrt_of_n ;i++){
        if( n%i == 0) return i;
    }
    return n;
}
 
void get_all_divisors(int n){
    if(n!=1){
        for(int i=get_lowest_divisor(n);i!=1;i=get_lowest_divisor(n=n/i)){
            cout << i << " ";
        }
    }else{
        cout << "1";
    }
}
 
int main () {
    int n;
    while (1){
        cout<<endl;
        cout<<"введем число(кроме 0) ";
        cin>>n;
        if( n==0)//если пользователь ввел 0 ,бесконечный цикл зав.
            break;
        get_all_divisors(n);
    }
    return 0;
}

@sergei60 · 24.07.2015, 19:15 **[ТС]**

Krasiosoft, а можно краткий ход вашей мысли. зачем изменения в цикле ф-ции get_all_divisors ?

@Krasiosoft · 24.07.2015, 19:24

Теперь функция get_lowest_divisor, если не смогла найти делитель, то она просто возвращает число, которое было передано в функцию. Т.е. если делителя нету, то делителем есть само это число.

А цикл в функции get_all_divisors теперь должен выходить по условию, если get_lowest_divisor вернет 1, т.к. единицу дальше некуда уже делить.

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@sergei60 50 / 31 / 11 Регистрация: 10.06.2012 Сообщений: 395
	23.07.2015, 20:44 [ТС]
	Krasiosoft, Спасибо большое (конечно лучше бы самому) ,но... Неясен длинный цикл ,пытаюсь разобраться. 0

@sergei60 50 / 31 / 11 Регистрация: 10.06.2012 Сообщений: 395
	24.07.2015, 19:15 [ТС]
	Krasiosoft, а можно краткий ход вашей мысли. зачем изменения в цикле ф-ции get_all_divisors ? 0

@Krasiosoft 52 / 52 / 23 Регистрация: 01.06.2015 Сообщений: 189
	24.07.2015, 19:24
	Теперь функция get_lowest_divisor, если не смогла найти делитель, то она просто возвращает число, которое было передано в функцию. Т.е. если делителя нету, то делителем есть само это число. А цикл в функции get_all_divisors теперь должен выходить по условию, если get_lowest_divisor вернет 1, т.к. единицу дальше некуда уже делить. 1

Разложение на простые множители без рекурсии

Решение