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

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

Войти
Регистрация
Восстановить пароль
 
Вакс Соня
0 / 0 / 0
Регистрация: 21.05.2013
Сообщений: 5
#1

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

21.05.2013, 20:39. Просмотров 510. Ответов 2
Метки нет (Все метки)

Здравствуйте. Для моей курсовой мне надо написать программу для нахождения НОК двух чисел через разложение на простые множители. Алгоритм такой, что раскладываем оба числа, потом выписываем разложение большего из чисел и умножаем его на недостающие множители из разложения другого числа. Как это реализовать? Расскладывать оба числа в разные массивы и потом сравнивать и находить недостающие множители? Или смотреть по большим степеням простых множителей?

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

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

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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     Нахождение НОК через факторизацию
Ответ Создать тему
Опции темы

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