Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.67
ActionDiman
0 / 0 / 0
Регистрация: 03.05.2014
Сообщений: 11
03.05.2014, 21:28     Разложение больших целых чисел на простые множители #1
Нужно написать программу, которая раскладывает числа на простые множители. Я знаю что теоретически надо проверять число на поочередное деление на все простые числа, т.е если число делиться на 2 поделить потом опять проверять на 2, если не делиться то на 3 , затем на 5 и т.д. Я просто не знаю как это записать в коде.Подскажите как реализовать это?
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
TenGen
Будущее рядом
 Аватар для TenGen
96 / 94 / 20
Регистрация: 06.03.2014
Сообщений: 342
03.05.2014, 21:48     Разложение больших целых чисел на простые множители #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
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;
}
Nanovenik
0 / 0 / 0
Регистрация: 05.08.2013
Сообщений: 4
03.05.2014, 22:10     Разложение больших целых чисел на простые множители #3
Еще есть формула под которую попадают все простые числа: (4х+-1) по ней можно заморочиться и создать программу которая будет раскладывать числа любого размера
ActionDiman
0 / 0 / 0
Регистрация: 03.05.2014
Сообщений: 11
03.05.2014, 23:12  [ТС]     Разложение больших целых чисел на простые множители #4
а можно ли сделать так чтобы самому с клавиатуры вводить числа, а не в коде писать?
TenGen
Будущее рядом
 Аватар для TenGen
96 / 94 / 20
Регистрация: 06.03.2014
Сообщений: 342
03.05.2014, 23:19     Разложение больших целых чисел на простые множители #5
ActionDiman, конечно. После объявления переменной х добавьте строки: cout << "Input number:"; cin >> x;
ActionDiman
0 / 0 / 0
Регистрация: 03.05.2014
Сообщений: 11
03.05.2014, 23:51  [ТС]     Разложение больших целых чисел на простые множители #6
А как сделать чтобы программа считала большие числа, ну скажем примерно 10 значные числа?
TenGen
Будущее рядом
 Аватар для TenGen
96 / 94 / 20
Регистрация: 06.03.2014
Сообщений: 342
04.05.2014, 08:42     Разложение больших целых чисел на простые множители #7
ActionDiman, измените int на что нибудь более емкое
Archi0
28 / 14 / 4
Регистрация: 18.07.2013
Сообщений: 164
04.05.2014, 11:13     Разложение больших целых чисел на простые множители #8
Таким методом до пенсии считать будет, если число очень большое иначе методы криптографии основанные на больших простых числах были бы просты к взлому. Для очень больших чисел нужно интересоваться другими методами поиска простого числа. Для знакового не простого числа int32 возможны всего 4792 простых делителя так, что заранее подготовленный массив простых чисел ускорит дело. Если проверять много чисел то неплохой вариант использовать 300 warp-ов Cuda (т.е сразу в 4792 потока).
Archi0
28 / 14 / 4
Регистрация: 18.07.2013
Сообщений: 164
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;
 }
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.05.2014, 18:38     Разложение больших целых чисел на простые множители
Еще ссылки по теме:

C++ Найти сумму целых положительных чисел больших a меньших b
C++ Разложить число на простые множители
Разложение на простые множители без рекурсии C++

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

Или воспользуйтесь поиском по форуму:
tegauss
30 / 24 / 24
Регистрация: 06.05.2014
Сообщений: 158
07.05.2014, 18:38     Разложение больших целых чисел на простые множители #10
ActionDiman, хинт:
1) при поиске делителей числа n, необходимо проверять не все числа из [1, n], а только из [1, sqrt(n)]
2) есть такая штука, как решето Эратосфена
Yandex
Объявления
07.05.2014, 18:38     Разложение больших целых чисел на простые множители
Ответ Создать тему
Опции темы

Текущее время: 03:37. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru