Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.64/22: Рейтинг темы: голосов - 22, средняя оценка - 4.64
0 / 0 / 0
Регистрация: 03.05.2014
Сообщений: 11
1

Разложение больших целых чисел на простые множители

03.05.2014, 21:28. Просмотров 4391. Ответов 9
Метки нет (Все метки)

Нужно написать программу, которая раскладывает числа на простые множители. Я знаю что теоретически надо проверять число на поочередное деление на все простые числа, т.е если число делиться на 2 поделить потом опять проверять на 2, если не делиться то на 3 , затем на 5 и т.д. Я просто не знаю как это записать в коде.Подскажите как реализовать это?
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
03.05.2014, 21:28
Ответы с готовыми решениями:

Разложение на простые множители*
Всем привет. Поможете с задачой только использвав <iostream> Задано натуральное число >= 2 ....

Разложение в простые множители
Дано натуральное число n. Требуется найти его разложение на простые множители. Формат выходных...

Разложение на простые множители
Требуется разложить целое число N на простые множители и вывести результат в порядке возрастания. ...

Разложение на простые множители*
Привет всем, помогите решить, если можно с комментариями что и как, буду очень благодарен, а то у...

9
Будущее рядом
101 / 100 / 48
Регистрация: 06.03.2014
Сообщений: 342
03.05.2014, 21:48 2
Лучший ответ Сообщение было отмечено ActionDiman как решение

Решение

ActionDiman, как то так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
 
using namespace std;
 
int main(int argc, char **argv)
{
    int x = 280, n[7] = {2, 3, 5, 7, 11, 13, 17};
    bool complete = false;
    while (!complete)
    {
        int i = -1; complete = true;
        while (i < 6)
            if (x%n[++i] == 0)
            {
                x /= n[i];
                cout << " " << n[i];
                complete = false;
                break;
            }
    }
    system("pause");
    return 0;
}
1
0 / 0 / 0
Регистрация: 05.08.2013
Сообщений: 4
03.05.2014, 22:10 3
Еще есть формула под которую попадают все простые числа: (4х+-1) по ней можно заморочиться и создать программу которая будет раскладывать числа любого размера
0
0 / 0 / 0
Регистрация: 03.05.2014
Сообщений: 11
03.05.2014, 23:12  [ТС] 4
а можно ли сделать так чтобы самому с клавиатуры вводить числа, а не в коде писать?
0
Будущее рядом
101 / 100 / 48
Регистрация: 06.03.2014
Сообщений: 342
03.05.2014, 23:19 5
ActionDiman, конечно. После объявления переменной х добавьте строки: cout << "Input number:"; cin >> x;
1
0 / 0 / 0
Регистрация: 03.05.2014
Сообщений: 11
03.05.2014, 23:51  [ТС] 6
А как сделать чтобы программа считала большие числа, ну скажем примерно 10 значные числа?
0
Будущее рядом
101 / 100 / 48
Регистрация: 06.03.2014
Сообщений: 342
04.05.2014, 08:42 7
ActionDiman, измените int на что нибудь более емкое
0
30 / 16 / 5
Регистрация: 18.07.2013
Сообщений: 220
04.05.2014, 11:13 8
Таким методом до пенсии считать будет, если число очень большое иначе методы криптографии основанные на больших простых числах были бы просты к взлому. Для очень больших чисел нужно интересоваться другими методами поиска простого числа. Для знакового не простого числа int32 возможны всего 4792 простых делителя так, что заранее подготовленный массив простых чисел ускорит дело. Если проверять много чисел то неплохой вариант использовать 300 warp-ов Cuda (т.е сразу в 4792 потока).
0
30 / 16 / 5
Регистрация: 18.07.2013
Сообщений: 220
07.05.2014, 16:00 9
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Prime
{
public:
    static const unsigned __int16 prime[];
    static bool IsPrime(__int32);
/********************************************
формат результата (знак числа)делитель -кратность +следующий делитель -кратность ...
отрицательные числа означающие кратность могут опускаться если множитель входит единожды
формат результата (знак числа)делитель +следующий делитель -кратность ...
максимум может понадобиться 13 чисел для описания факторизации числа __int32
функция возвращает false для -1 0 1 которые не может разложить никак не меняя значения
по указателю __int32*
********************************************/
    static bool Prime::factorization (__int32 num, __int32* rez);
    Prime(void);
    ~Prime(void);
};
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
const unsigned __int16 Prime::prime[4793] = {
    2,3,...их тут много...,46337,1
};
 
Prime::Prime(void)
{
}
 
Prime::~Prime(void)
{
}
 
bool Prime::IsPrime(__int32 num)
{
    if (num<4 && num>-4 && num!=0) return true; // отсеяны числа -3 -2 -1 1 2 3
    if ((num&1)==0) return false; // отсеяны все чётные и 0 кроме -2 2
    if (num%3==0) return false; // отсеяны все кратные 3 кроме -3 3
    //66.67% чисел отсеяно
    __int32  probationer = num<0?-num:num;
    if (probationer <= prime[4791])
    {
        int i;
        int j;
        //первое деление секции не симметричное так как маленькие простые числа встречаются чаще.
        if(probationer>330) 
        {
            i=67;
            j=4790;
            if (probationer==331 || probationer==46337) return true;
        }
        else 
        {
            i=3;
            j=64;
            if (probationer==5 || probationer == 317) return true;
        }
        //поиск числа в массиве
        while (i<j)
        {
            int m = (i+j)>>1;
            unsigned __int16 p = prime[m];
            if(probationer==p) return true;
            if(probationer>p) i=++m; else j=--m;
        }
        return probationer==prime[i];
    }
    else
    {
        const unsigned __int16* p= &prime[2];//массив должен заканчиваться на 1
        while (true) 
        {
            if (probationer%*p==0) {//данная операция служит заодно и проверкой на конец массива
                if (*p==1) return true; else return false;
            }
            else
            {
                if (*p**p>probationer) return true;
            }
            p++;
        }
    }
}
 
 bool Prime::factorization (__int32 num, __int32* rez) 
 {
     if (num<1 && num>-1 ) return false; 
     __int32  probationer = num<0?-num:num;
     const unsigned __int16* p= prime;
     __int32* prez = rez;
     while (*p!=1) 
    {
        int count =0;
        if (probationer%*p==0)
        {
            probationer/=*p;
            --count;
            *prez++=*p;
            while(probationer%*p==0)
            {
                probationer/=*p;
                --count;
            }
            if (count<-1) *prez++ = count;
        }
        else
        {
            if (*p**p>probationer) // в данной ситуации сам probationer это последний делитель и его кратность равна 1
            {
                if(probationer!=1) *prez = probationer;
                if (num>0) return true; else {*rez = -*rez; return true;}
            }
            else
            {
                p++;
            }
        }
    }
    //  простое число по модулю большее чем 2147117570 например 2^31-1
    *rez=num; return true;
 }
0
30 / 24 / 27
Регистрация: 06.05.2014
Сообщений: 161
07.05.2014, 18:38 10
ActionDiman, хинт:
1) при поиске делителей числа n, необходимо проверять не все числа из [1, n], а только из [1, sqrt(n)]
2) есть такая штука, как решето Эратосфена
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
07.05.2014, 18:38

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Разложение числа на простые множители
Дано натуральное число n ≥ 2. Составить программу разложения этого числа на простые множители:...

Разложение натурального числа на простые множители
Выведите разложение натурального числа n &gt; 1 на простые множители. Простые множители должны быть...

Разложение на простые множители без рекурсии
Задача такая : Надо написать две функции get_all_divisorts и get_lowest_divisor. Функция main...

Разложение числа на простые множители (упрощенная). Зацикливание?
Добрый вечер. Написал небольшой код для разложения небольших чисел на простые цифры. По умолчанию...


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

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

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