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

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

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

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

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

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

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

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

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

нахождение НОК - C++
Подскажите как найти НОК значений с плавающей точкой.

Нахождение суммы s(x) через for - C++
s(x) = ∑ (-1)^k * ((1+x)^2k)/k s(x)=\sum {(-1)}^{k}\frac{({1+x)}^{2k}}{k}

Нахождение среднего числа, через if else - C++
Помогите разобраться с этим, придумал алгоритм через ветвление, но не получилось до конца его реализовать, первые 2 работают, 3 блок не...

Нахождение площади через координаты треугольника - C++
Здравствуйте, есть задание Напишите функцию square, вычисляющую площадь треугольника. С ее помощью для каждой из N точек определите,...

Нахождение определителя матрицы через рекурсию - C++
Помогите, пожалуйста, реализовать на с программу нахождения определителя матрицы.

Нахождение дискриминанта через указатели и ссылки - C++
Имеется вот такой код #include <iostream> #include <math.h> using namespace std; int menu() { int choose; cout...

Нахождение корней квадратного уравнения через дискриминант - C++
Здравствуйте! Начинаю работать в C++ Builder 3.1 в DOSBOXe. Стоит задача реализовать программу нахождения корней квадратного уравнения...

Нахождение максимального и минимального из трех чисел (через if) - C++
напишите условие нахождения максимального и минимального трех чисел через if,else if,else


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

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

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