VPF::Нахождение простых делителей заданного числа

pacantre

Дата 24.4.2012, 15:29 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 1
Регистрация: 24.4.2012

Репутация: нет
Всего: нет

Задача из сборника Златопольского

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

Код

#include <iostream>
using namespace std;
 
int main ()
{
    setlocale (LC_CTYPE, "Russian");
    int n;
    cout<<"Введите число, дял которого искать простые делители: ";
    cin>>n;
 
    for (int counter_1 = 1; counter_1 <= n; counter_1++) // Цикл для нахождения делителей числа n
    {
        int k = 0;
        
        if (n % counter_1 == 0) // Если это условие выполняется, то число counter_1 - делитель числа n
        {
            for (int counter_2 = 2; counter_2 < counter_1; counter_2++)//Цикл для наождения простых делителей числа n
            {
                 k = 0; //K обнуляется на каждой итерации
                if (counter_1 % counter_2 == 0) // Если counter_1 % counter_2 без остатка, то counter_1 не простой делитель
                {
                    k++;
                    
                }
                
                
            }
 
        }
        if (k == 0) //Если k не изменилось ни разу, то условие if (counter_1 % counter_2 == 0) не выполнилось ни разу, 
                    //значит counter_1 делится только на 1 и на самого себя, значит counter_1 простое
                    {
cout<<"Делитель "<<counter_1<<" простой"<<"\n";
                    }
        
    }
    
    
    
    return 0;
}

Выводит не простые делители, а все числа от 1го до n

Объясните как правильно

Это сообщение отредактировал(а) bsa - 24.4.2012, 16:10

bsa

Дата 24.4.2012, 16:07 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

В строке 14 замени 0 на -1;

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

baldina

Дата 24.4.2012, 17:10 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 15
Всего: 101

строка 14 пустая

Добавлено @ 17:20
pacantre, нужно проверку

Цитата(pacantre @ 24.4.2012, 15:29

)

if (k == 0) //Если k не изменилось ни разу, то условие if (counter_1 % counter_2 == 0) не выполнилось ни разу,

перенести выше, внутрь цикла проверки if. иначе получается, что k==0 даже если это не простой делитель.
у тебя еще одна ошибка: число 1 простым не считается, поэтому внешний цикл надо начинать от 2

Это сообщение отредактировал(а) baldina - 24.4.2012, 17:22

disputant

Дата 24.4.2012, 18:29 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 210
Регистрация: 28.11.2011

Репутация: нет
Всего: 3

Хочу только добавить, что нет НИКАКОГО смысла перебирать подряд числа от 1 до n в поисках делителей... До sqrt(n) достаточно (подумайте сами, почему), и только 2 и нечетные (опять же очевидно, почему). А еще лучше не просто нечетные, а нечетные вида 6k+1, 6k-1. Тогда работать ваша программа будет явно пошустрее smile

Опять же - к чему вторая проверка? Представим, что ваше число делится на какое-то. Но вы УЖЕ прооверили делимость на все меньшие, верно? так что ваш найденный делитель уже ни на что делиться не будет...

На коленке за 5 минут smile

- что-то вроде этого:

Код



#include <iostream>
#include <iomanip>

using namespace std;


int main(int argc, const char * argv[])
{
    int n;
    cout << "Введите число: ";
    cin >> n;

    cout << n << " = ";

    // Убираем 2 и 3, не подпадающие под 6k+-1
    while(n%2 == 0) {
        n/= 2;
        cout << "2 * ";
    }
    while(n%3 == 0) {
        n/= 3;
        cout << "3 * ";
    }

    while(n > 1)
    {
        bool notfound = true;
        for(int k = 1; (6*k-1)*(6*k-1) <= n; ++k)
        {
            int p = 6*k - 1;
            if (n%p == 0)
            {
                n /= p;
                cout << p << " * ";
                notfound = false;
                break;
            }
            p += 2;
            if (n%p == 0)
            {
                n /= p;
                cout << p << " * ";
                notfound = false;
                break;
            }
        }
        if (notfound) break;
    }

    cout << n << endl;
}

Это сообщение отредактировал(а) disputant - 24.4.2012, 18:42

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »