[C++] Rozkład liczby na czynniki pierwsze

[rochaj]

W jaki sposób rozwiązać taki problem: użytkownik podaje lilczbe naturalną \(\displaystyle{ >2}\), a program wyświetla ją w takiej postaci np. dla \(\displaystyle{ 6}\) to będzie 2*3, dla \(\displaystyle{ 8}\) będzie 2^3, a np. dla \(\displaystyle{ 20}\) to będzie 2^2*5.

[Vardamir]

Do poczytania: faktoryzacja liczb. Jest tego naprawdę od groma w internecie, ponieważ jest to jeden z podstawowych problemów algorytmicznych.

[rochaj]

Tyle to akurat wiem, bo myślałem i próbowałem go rozwiązać. No to może tak : mam w sumie ten program, ale problemem jest to że * występuje na końcu a nie powinno jej być i że np. jak wpisuje liczbe \(\displaystyle{ 6}\) to mam wynik 2^1*3^1* a powinno być 2*3, więc nie powinno być bez ^1.

Kod: Zaznacz cały

#include <cmath>
#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
  int a[40],i,d,m,n;

  cin >> n;

    i = 0; m = (int)sqrt(n);
    for(d = 2; d <= m; d++)
      while((n % d) == 0)
      {
        a[++i] = d;
        n /= d;
      };
    if(n > 1) a[++i] = n;

for(int i=1,count=0;i<=d;++i)
  {
   if((!i)||((i!=d)&&(a[i-1]==a[i]))) ++count;
   
   else
     {
     if (count!=0)
      {
      	
      cout<<a[i-1]<<'^'<<count<<'*';}
      count=1;
     }
  }

return 0;
}

[Vardamir]

Na razie takie uwaga, nie magazynuj informacji o poszczególnych czynnikach. Chodzi mi o tą tabelę, jest zbędna. Wypisywanie możesz przeprowadzić od razu po zliczeniu ile razy uda Ci się podzielić podaną liczbę przez kolejny czynnik.

Ogólna idea:

Kod: Zaznacz cały

Podajemy n
Dla d=2 do d=n/2
licznik=0
Dopóki n podzielna przez d, podziel przez d i zwiększ licznik
Gdy n nie jest już podzielna przez d, jeśli licznik>1 wypisz 'd^licznik'
Jeśli n>1 wypisz '*'

Druga sprawa, jeśli nie wiesz co się dzieje w kodzie - odpal debbuger i analizuj linijka po linijce z debbugerem.

Edit. Program powinien mieć ok 10-20 linijek.

[rochaj]

jak odpalać debugger w dev?

[Vardamir]

Nie wiem, nie używałem tego nigdy. Ale google na pewno pomoże.

Jednak radziłbym Ci się jeszcze raz zastanowić nad tym zadaniem. Można je napisać czytelnie w 10 linijkach bez żadnych tablic z 4 zmiennymi.

[rochaj]

czyli według tego algorytmu co napisałes

[Vardamir]

Na przykład. Choć było to na kolanie robione. Teraz jak napisałem już ten program to wygląda u mnie tak:

Kod: Zaznacz cały

Podajemy n
Dla d=2, dopóki n>1 wykonaj 3-6, a następnie ++d
Dla licznik=0, dopóki n podzielne przez d, zwiększ licznik o jednej, a następnie n/=d
Jeśli licznik>0 wypisz 'd'
Jeśli licznik>1 wypisz '^licznik'
Jeśli n>1 i licznik >0 wypisz '*'

[rochaj]

ok próbuje to przełozyc na język c++ (to moje początki jakby co)
czy 2. "Dla d=2, dopóki n>1 wykonaj 3-6, a następnie ++d" chodzi o to

Kod: Zaznacz cały

 int d=2;
    while (n>1)
    {

    	    } 
    d++;

??

[Vardamir]

Blisko, tylko inkrementacja w środku pętli

Kod: Zaznacz cały

 int d=2;
    while (n>1)
    {
    //tutaj wykonujemy 3-6
    d++;
    } 

Można to też zapisać jako pętle for, będzie wtedy czytelniejsze:

Kod: Zaznacz cały

for (int d = 2; n>1; ++d) {
//tutaj wykonujemy 3-6
}

[rochaj]

a te instrukcje od 4 do 6 to po prostu zrealizować if-ami?

[Vardamir]

Tak.

[rochaj]

czyli tak?

Kod: Zaznacz cały

if (licznik>0) cout<<d;
         if (licznik>1) cout<<"^"<<licznik;
         if (n>1 && licznik >0) cout<<"*";

[Vardamir]

Zgadza się, złóż to wszystko razem i przetestuj. Masz już wszytko gotowe.

[rochaj]

no efekt jest taki ale nie działa do końca dobrze bo np. dla \(\displaystyle{ 6}\) podaje wynik 2*3^2

Kod: Zaznacz cały

#include<iostream>
#include<cstdlib>
#include<cmath>
using namespace std;
 
int main()
{
    int n,licznik=0;
    cin>>n;
    int d=2;
    while (n>1)
    {
    	while(n%d==0) 
                {
                        licznik++;
                        n/=d;
                }
         if (licznik>0) cout<<d;
         if (licznik>1) cout<<"^"<<licznik;
         if (n>1 && licznik >0) cout<<"*";
        d++;
    } 
    
      
        return 0;
}