Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

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

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

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

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

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

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

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

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

Разложение на простые множители заданного натурального числа - C++
Составить программу , печатающую разложение на простые мн0жители заданн0го натУральн0го числа n > 0 (другими словами требуется печатать...

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

9
TenGen
Будущее рядом
98 / 96 / 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;
}
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
Будущее рядом
98 / 96 / 20
Регистрация: 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
Будущее рядом
98 / 96 / 20
Регистрация: 06.03.2014
Сообщений: 342
04.05.2014, 08:42 #7
ActionDiman, измените int на что нибудь более емкое
0
Archi0
28 / 14 / 4
Регистрация: 18.07.2013
Сообщений: 170
04.05.2014, 11:13 #8
Таким методом до пенсии считать будет, если число очень большое иначе методы криптографии основанные на больших простых числах были бы просты к взлому. Для очень больших чисел нужно интересоваться другими методами поиска простого числа. Для знакового не простого числа int32 возможны всего 4792 простых делителя так, что заранее подготовленный массив простых чисел ускорит дело. Если проверять много чисел то неплохой вариант использовать 300 warp-ов Cuda (т.е сразу в 4792 потока).
0
Archi0
28 / 14 / 4
Регистрация: 18.07.2013
Сообщений: 170
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 / 24
Регистрация: 06.05.2014
Сообщений: 158
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
Привет! Вот еще темы с ответами:

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

Разложение числа на множители - C++
var s1,s2,n: longint; f: integer; begin write('vvedite natural chislo '); readln(n); f:=0; s1:=1; ...

Найти разложение натурального числа на сумму квадратов трёх целых чисел - C++
Для заданного натурального N (0 &lt; N ≤ 10^9) вычислить число троек целых чисел (x, y, z), таких, что x^2 + y^2 + z^2 = N. Помогите...

Найти сумму целых положительных чисел больших a меньших b - C++
числа а и b вводятся в консоли


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

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

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