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

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

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

Нужно написать программу, которая раскладывает числа на простые множители. Я знаю что теоретически надо проверять число на поочередное деление на все простые числа, т.е если число делиться на 2 поделить потом опять проверять на 2, если не делиться то на 3 , затем на 5 и т.д. Я просто не знаю как это записать в коде.Подскажите как реализовать это?
http://www.cyberforum.ru/cpp-beginners/thread1908705.html
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.05.2014, 21:28
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Разложение больших целых чисел на простые множители (C++):

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

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

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

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

Разложение на простые множители заданного натурального числа
Составить программу , печатающую разложение на простые мн0жители заданн0го...

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

Описать функцию, находящую разложение заданного натурального числа на простые множители
Помогите написать программу, пожалуйста Описать функцию factors(a, n, F),...

Разложение числа на множители
var s1,s2,n: longint; f: integer; begin write('vvedite natural...

Разложение числа на множители
Всем привет, надо разложить число на множители(определенные). С маленькими...

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


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

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

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