Wyciąganie liczby poza pierwiastek. Rozkład na czynniki.

Question

Witam,

Na sam początek opiszę co chce zrobić i co d tej pory zrobiłem. Chce napisać taki algorytm, który np. z liczby sqrt(18), zrobi liczbę 3sqrt(2), wynika to z rozkładu:

Zrobiłem mapowanie tych czynników, tylko, że mój program robi coś takiego:

#include <iostream>
#include <vector>
#include <map>

using namespace std;
using vi=std::vector<int>;
using mii=std::map<int,int>;

int lastprime(vi & primes){
   // bool isprimre=true;
    auto it=primes.begin();
    auto end=primes.end();
    int i=primes.back()+1;
    for (;it!=end;i++)
    for(it=primes.begin();it!=end;it++){
        if(i%(*it)==0) {
            break;}
    }i--;
    primes.push_back(i);
    return i;
}

int main()
{
    vi v{2};
    mii m {};
    int num=15593760;
    while (num!=1 ){
        int currentnum=v.back();
    while (num%currentnum==0){
        m[currentnum]++;
        num/=currentnum;
    } 
        lastprime(v);
    }
     for(const auto &x:m) std::cout << x.first<< " wystepuje "<<x.second<<" razy"<<std::endl;
     std::cout<< std::endl; 
    while (lastprime(v)<10);
   // for(const auto &x:v) std::cout << x<<' ';
    std::cout<< std::endl;
    return 0;
}

W skrócie wypisuje ilość czynników po rozkładzie.

Dla liczby 32, nie ma problemów, gdyż przy rozkładzie będą same dwójki. Ale przy 18 mamy różne liczby pierwsze 3 i 2. Jak zrobić operację na tych liczbach, żeby wyciągnąć tą liczbę poza pierwiastek. Może szukać tych samych liczb i potęgować je (wykładnik potęgi będzie równy ilości tych samych liczb). 

Czy ktoś wie jak to zrobić? Ja już nie mam pomysłów :(.

 

Z góry bardzo dziękuje. 

Comments

Mając rozkład masz już wszystko. Pierwiastkowanie to nic innego jak potęgowanie liczby przez pewną odwrotność, w ogólności pierwiastek n-tego stopnia z liczby m można zapisać jako m^{1/n}. 

Bazując na tym co napisałem, wystarczy sprawdzać, czy wykładnik jest większy niż stopień pierwiastka. Jeśli jest, to wystarczy użyć chociażby operacji modulo. A jak nie jest, to nie ma nawet co robić. 

---

Czyli mam zrobić pętle czy jak, dla liczby 18

18/2 = 9

9/3 = 3

3/3 = 1

czyli mamy czynniki: 2,3,3.

I teraz co mam zrobić?

---

No nie, co innego napisałem. Masz już gotowy rozkład, więc dla każdej z podstaw (liczby 2 oraz 3) przechodzisz po ich wykładnikach (liczby 1 oraz 2). To jest prosty algorytm, którego w zasadzie używasz, jak wyciągasz liczbę spod pierwiastka.

---

już trochę rozumiem, spróbuje napisać w c++ :)

---

Ciężko mi to napisać, czy możesz mi pokazać to na przykładzie ?

---

->tu

Sorki admins, też cieszę się jak dostaję gotowca [w prostych rzeczach]. Jak coś potrafię to wolę sam.

---

dzięki, sorki, ale próbowałem napisać ale wychodziły głupoty :(.