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

Проверка числа на простоту и разложение на простые множители - C++

Восстановить пароль Регистрация
 
zer0mail
2176 / 1859 / 187
Регистрация: 03.07.2012
Сообщений: 6,615
Записей в блоге: 1
07.02.2016, 13:57     Проверка числа на простоту и разложение на простые множители #1
Функции проверки числа на простоту, поиск минимального простого делителя и разложения на простые множители.
Ниже n - число, которое надо проверить или разложить. Хотя в математике 0 и 1 не являтся ни простыми ни составными, здесь они считаются простыми, т.е. их разложение состоит из одного множителя - их самих. С другой стороны, в отличии от настоящих простых чисел, они не участвуют в разложении на множители других натуральных n.

Отдельной функции проверки на простоту нет - в качестве нее можно использовать функцию поиска минимального простого делителя, которая возвращает 0, если число простое (в т.ч. 0 или 1).
При разложении числа простые множители запишутся в массив в порядке неубывания следующим образом:
C++
1
2
3
4
5
6
7
Число Разложение              
0      0
1      1 
31     31
72     2,2,2,9,9
1000   2,2,2,5,5,5
1024   2,2,2,2,2,2,2,2,2,2
Если надо сгруппировать разложение, то есть функция преобразования:
C++
1
2
3
4
5
6
7
Число Сгруппированное разложение  (в массиве пары:  количество  множителей, множитель)            
0      1,0
1      1,1
31     1,31
72     3,2,2,3
1000   3,2,3,5
1024   10,2
Функции

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
// Если компилятор не понимает size_t, раскомментируйте следующую строку:
// typedef unsigned size_t; 
 
// Возвращает минимальный простой делитель числа n или 0, если число простое.
// Можно использовать, как функцию проверки n на простоту (0 / не0).
unsigned minprostdel(unsigned n)
{
    unsigned d;
    // для чисел 0,1,2,3 вернем 0
    if (n<4) {
        return 0;
    }
    // для четных>2 вернем 2
    if (!(n&1)) {
        return 2;
    }
    // теперь проверяем нечетные, не превышающие корня из n
    for (d=3;d*d<=n;d+=2) {
        if(n%d==0) 
            // делитель найден
            return d;
    }
    return 0; // значит, число n простое >3
    
}
// Разложение числа n на простые множители. Каждый множитель записывается в массив arr (могут быть дубли).
// Функция возвращает индекс последнего записанного элемента в arr.
// Если n простое, функция возвращает 0 и записывает n в arr.
// arr должен вмещать все делители (которые могут повторяться), поэтому: 
// для 4-х байтового n размер arr>=32 байта, для 8-ми байтового n размер arr>=64 байта
 
size_t razlprosta(unsigned n, unsigned *arr)
{
    unsigned d;
    size_t i=0; // индекс в массиве, куда пишем делители n (они же множители в разложении n)
    // для чисел 0,1,2,3 вернем 0
    if (n<4) {
        arr[0]=n;
        return 0;
    }
    // сначала степени 2-ки, единственное четное простое
    // анализируем младший бит
    while(!(n&1)) {
        arr[i++]=2;
        n>>=1;
    }
    // теперь нечетные, не превышающие корня из n
    for (d=3;d*d<=n;d+=2) {
        while(n%d==0) {
            // n делится на d
            arr[i++]=d;
            n/=d; // уменьшаем n, заодно сокращая диапазон для d
        }
    }
    if (n>1)
        arr[i++]=n; // последний множитель (или само число, если n было простым)
    return --i;     // вернем индекс последнего записанного элемента
    
}
// Функция группирует одинаковые множители в разложении на простые множители и 
// возвращает количество различных простых делителей в разложении (количество пар)
// Разложение на простые из массива arr переносятся в массив comp парами: количество, множитель
// Параметр k - индекс последнего записанного элемента arr.
// Для корректной работы массивы arr и comp не должны перекрываться.
size_t comprazla(unsigned *comp, size_t k, const unsigned *arr)
{
    size_t i,j=1;
    // 1 элемент всяко есть, занесем его
    comp[0]=1;
    comp[1]=arr[0];
    
    for (i=1;i<=k;++i) {
        if(comp[j]==arr[i])
            // делитель повторяется, увеличим счетчик
            ++comp[j-1];
        else {
            // новый делитель
            comp[++j]=1;
            comp[++j]=arr[i];
        }
    }
    return ++j/2;
}

простой тест работы функций

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int main(int argc, char *argv[])
{
    unsigned a[]={0,1,2,4,8,6,12,25,31,36,72,1000,1024,4000000000};
    unsigned arr[32];  // массив для разложений с дублями
    unsigned comp[32]; // массив для разложения с группировками
    for (int i=0;i<sizeof(a)/sizeof(int);++i) 
    {
        cout<<a[i]<<" minprost="<<minprostdel(a[i])<<" ";
        size_t k=razlprosta(a[i],arr);
        for(int j=0;j<=k;++j)
            cout<<arr[j]<<"*";
        cout<<"  --  ";
        k=comprazla(comp, k, arr);
        for(int j=0;j<k;j++)
            cout<<comp[2*j+1]<<"^"<<comp[2*j]<<" ";
        cout<<endl;
    } 
    return 0;              
}
результат работы теста

0 minprost=0 0* -- 0^1
1 minprost=0 1* -- 1^1
2 minprost=0 2* -- 2^1
4 minprost=2 2*2* -- 2^2
8 minprost=2 2*2*2* -- 2^3
6 minprost=2 2*3* -- 2^1 3^1
12 minprost=2 2*2*3* -- 2^2 3^1
25 minprost=5 5*5* -- 5^2
31 minprost=0 31* -- 31^1
36 minprost=2 2*2*3*3* -- 2^2 3^2
72 minprost=2 2*2*2*3*3* -- 2^3 3^2
1000 minprost=2 2*2*2*5*5*5* -- 2^3 5^3
1024 minprost=2 2*2*2*2*2*2*2*2*2*2* -- 2^10
4000000000 minprost=2 2*2*2*2*2*2*2*2*2*2*2*5*5*5*5*5*5*5*5*5* -- 2^11 5^9
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.02.2016, 13:57     Проверка числа на простоту и разложение на простые множители
Посмотрите здесь:

C++ Проверка числа на простоту
Разложение числа на простые множители (упрощенная). Зацикливание? C++
C++ Проверка числа на простоту
C++ Разложение больших целых чисел на простые множители
C++ Проверка числа на простоту
Разложение на простые множители без рекурсии C++
Разложение натурального числа на простые множители C++
C++ Проверка числа на простоту

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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