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

Нахождение НОК через факторизацию - C++

Восстановить пароль Регистрация
 
Вакс Соня
0 / 0 / 0
Регистрация: 21.05.2013
Сообщений: 5
21.05.2013, 20:39     Нахождение НОК через факторизацию #1
Здравствуйте. Для моей курсовой мне надо написать программу для нахождения НОК двух чисел через разложение на простые множители. Алгоритм такой, что раскладываем оба числа, потом выписываем разложение большего из чисел и умножаем его на недостающие множители из разложения другого числа. Как это реализовать? Расскладывать оба числа в разные массивы и потом сравнивать и находить недостающие множители? Или смотреть по большим степеням простых множителей?

Добавлено через 15 минут
Помогите(((
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.05.2013, 20:39     Нахождение НОК через факторизацию
Посмотрите здесь:

C++ Нахождение определителя матрицы через рекурсию
нахождение НОК C++
C++ нахождение нод и нок двух чисел на С++
Нахождение площади через координаты треугольника C++
Нахождение основных значений оформить через функцию RESHENIE(), ввод данных и вывод на печать через функцию MAIN() C++
C++ Нахождение дискриминанта через указатели и ссылки
Разработать класс "Cmp", обеспечивающий нахождение НОД и НОК двух чисел C++
C++ Нахождение корней квадратного уравнения через дискриминант

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
21.05.2013, 21:09     Нахождение НОК через факторизацию #2
Вакс Соня, вот код факторизации числа N
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"
#include "cmath"
 
using namespace std;
 
long long n;
int t;
void fact(int i) {
    t=0;
    while (n%i == 0) { t++; n /= i; }
    if (t > 0) printf("%d %d\n",i,t);
}
 
int main() {
    cin >> n;
    int k = int(sqrt(double(n)));
    fact(2);
    for (int i = 3; i <= k; i += 2) {
        fact(i);
        if (n == 1) break;
    }
    if (n > 1) cout << n << " 1";
}
Добавлено через 5 минут
Вакс Соня, записать разложение большего в set, а затем при разложении меньшего проверять его существование в set, в случае отсутствия -- умножать.

Добавлено через 6 минут
Вакс Соня, вот тут решеньице завалялось. Сначала вводится n, затем n чисел и ищется НОК для всех
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
#include <cstdio>
#include <cmath>
#include <map>
 
using namespace std;
 
void main(){
    int n;
    map<int, int> a;
    scanf("%d", &n);
 
    for (int i=0; i<n; i++){
        int v;
        scanf("%d", &v);
        int j=2;
        while (j < sqrt((double)v)+1){
            int s=0;
            while(!(v%j)){
                s++;
                v/=j;
            }
            if (s > 0 && a[j] < s){
                a[j] = s;
            }
            j++;
        }
        if (a[v] == 0) a[v]++;
    }
    
    long int s=1;
    for (map<int, int>::iterator it=a.begin(); it!=a.end(); it++){
        for (int i=0; i<it->second; i++){
            s*=it->first;
        }
    }
    printf("%d", s);
}
Вакс Соня
0 / 0 / 0
Регистрация: 21.05.2013
Сообщений: 5
23.05.2013, 12:35  [ТС]     Нахождение НОК через факторизацию #3
Спасибо!) Это то, что нужно))
Yandex
Объявления
23.05.2013, 12:35     Нахождение НОК через факторизацию
Ответ Создать тему
Опции темы

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