Matematické Fórum

rtio · 05. 12. 2009 13:27

Nevím si rady s tímto příkladem:

Mám napsat program, který vypíše rozklad daného přirozeného čísla z intervalu 2 do
10000, včetně, na prvočinitele. Po spuštění programu, uživatel zadá číslo a
program vytiskne příslušný rozklad.

Kdyby se někdo našel byl bych moc rád, docela v tom plavu.

gladiator01

třeba takhle, ale jde to i jinak:

Code:

#include<iostream> 

using namespace std;

void Rozklad(int hodnota)
{
    int delitel=2;
    if(hodnota>1)
    {
       while(hodnota%delitel !=0)
          delitel++;
       cout << delitel << " ";
       Rozklad(hodnota/delitel);
    }
}

int main()
{
  int x=0;
  cout << "Zadej cislo <2-10 000>: ";
  cin >> x;
  
  Rozklad(x);
  cout << endl;
   
  system("pause");
  return 0;
}

Kondr · 05. 12. 2009 13:56

Drobné zrychlení dosáhneme, když zrušíme rekurzi a nebudeme možné dělitele procházet vždy znovu od dvojky:

Code:

void Rozklad(int hodnota)
{
    int delitel=2;
    while(hodnota>1)
    {
       while(hodnota%delitel !=0)
          delitel++;
       cout << delitel << " ";
       hodnota=hodnota/delitel;
    }
}

Další zrychlení (netestovat sudé dělitele větší než 2, ...) mohou prodloužit kód.

Olin · 05. 12. 2009 16:54

Testoval bych dělitelnost jen po odmocninu, tím se to zrychlí zejména pro velká prvočísla.

zlamal89

Autor zapomel dodat ze by mel vystup vypadat nejak takhle
2 = 2^1
3 = 3^1
4 = 2^2
5 = 5^1
6 = 2^1 * 3^1
7 = 7^1
8 = 2^3
9 = 3^2
10 = 2^1 * 5^1
11 = 11^1
12 = 2^2 * 3^1
.....
1768 = 2^3 * 13 * 17
.....
10000 = 2^4 * 5^4
a to uz nevim ani ja jak napsat:D jestli nekdo vi tak mi pls poradte muzete i mail zlamal89@seznam.cz

Olin · 08. 12. 2009 11:29

Stačí si pamatovat, kolikrát už jsme měli to dané prvočíslo. Výhodné může být to, že výše popsané algoritmy vypisují ta prvočísla setříděně od nejmenšího po největší.

zlamal89

POrad nevim jak to napsat jsem pouhy zacatecnik a jeste toho moc neumim:D moc prosim lidi pomozte mi

gladiator01

Tady jsem něco sesmolila, doufám, že mě Kondr neukamenuje.
Pro některá čísla mi nechtěl fungovat výpis proto to je takové zvláštní.

Code:

void Rozklad(int hodnota)
{
    int p[50][2];
    int pocet=0,i=0,h=0;
    int delitel=2;
    if(hodnota==4)
      cout << "2^" << "2";
    if(hodnota%2==0) //když rozklad začíná na 2
    {
      p[0][0]=delitel;
      p[0][1]=pocet;
      i=1;
      pocet=0;
    }
    while(hodnota>sqrt(delitel))
    {
       while(hodnota%delitel!=0)
       {
          delitel++;
          pocet=0;
       }
       pocet++;
       p[i][0]=delitel;
       p[i][1]=pocet;
       if(hodnota%delitel==0)
         i++;
       hodnota=hodnota/delitel;
    }
    for(int j=0; j<i; j++)
    { 
       if(p[j][0]!=p[j+1][0])
          cout << p[j][0] << "^" << p[j][1] << " * ";
    }
}

zlamal89 · 08. 12. 2009 20:13

Dik za snahu ale nejede ti to mas tam nejake errory 7 a 15 radek:-) ale jinak dobre

gladiator01

mě to funguje

nezapomněl jsi si přidat knihovnu math.h kvůli fci sqrt (u prvního while)?

co ti to hlásí?

zlamal89 · 08. 12. 2009 21:02

To bude ono presne tak neamm tam tu knihovnu protoze jsem ji jeste nikdy nevidel to bude tim:D, rikam ze jsem zacatecnik a bereme poze zaklady potreboval bych to napsat jenom v C a ne v C++ a trosicku logicteji protozne v tomhle se moc nevyznam

Kondr · 08. 12. 2009 21:04

↑ gladiator01:kamenovat se nebude, ale ten program má mouchy ... rozhodně místo
while(hodnota>sqrt(delitel))
má být
while(hodnota>=delitel*delitel)

Proč se dvojka řeší zvlášť? K čemu test if(hodnota%delitel==0) (to musí být splněné kvůli while cyklu) Proč se u sudžch čísel podruhé inicializuje pocet na 0? Co to udělá pro čísla dělitelná 4?

gladiator01

Je to celé nějaké vadné.

to if(hodnota%delitel==0) je tam opravdu k ničemu

Tohle tam je protože když dám 12 tak se mi rozklad nevypíše (částečně).

Code:

 
    if(hodnota%2==0) 
    {
      p[0][0]=delitel;
      p[0][1]=pocet;
      i=1;
    }

Code:

void Rozklad(int hodnota)
{
    int p[50][2];
    int pocet=0,i=0,h=0;
    int delitel=2;

    if(hodnota%2==0) //když rozklad začíná na 2
    {
      p[0][0]=delitel;
      p[0][1]=pocet;
      i=1;
    }


    while(hodnota>1)
    {
       while(hodnota%delitel!=0)
       {
          delitel++;
          pocet=0;
       }
       pocet++;
       p[i][0]=delitel;
       p[i][1]=pocet;
       i++;
       hodnota=hodnota/delitel;
    }
    for(int j=0; j<i; j++)
    { 
       if(p[j][0]!=p[j+1][0])
          cout << p[j][0] << "^" << p[j][1] << " * ";
    }
}

mobby · 12. 12. 2009 15:37

Zdravím vás :)

mám obdobný problém s tím že bych tam měl zakomponovat prvočísla do 10000 (které si vypočítám na začátku nebo napevno z pole nebo ze souboru) a vůbec nevím jak na to sem začatečník :(

Tady přikládám kompletní zadání projektu který mám udělat ... kdyby mi stím někdo pomohl nebo poradil zda stačí nejak přepsat kod který je výš, prosím ?

mobby · 12. 12. 2009 20:21

Zkusil jsem kod (který je víš) předělat aby to používalo prvočísla zadané v poli (zmenšil sem aspon na ted rozsah do 100) ale to by přece nemělo mít žádný vliv na funkčnost a přesto mi některé čísla jako je 64 nebo 84 nefungují nevíte kde je chyba??

Code:

# include <stdio.h>
# include <iostream>
    using namespace std;
# include <iomanip>


int const PP =25;


void Rozklad(int hodnota)
{
    int p[50][2];
    int pocet=0,i=0,h=0,z=0;
    int delitel=2;
    int pole[PP] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};


    if(hodnota%2==0) //když rozklad začíná na 2
    {
      p[0][0]=pole[z];
      p[0][1]=pocet;
      i=1;
    }


    while(hodnota>1)
    {
       while(hodnota%pole[z]!=0)
       {
          z++;
          pocet=0;
       }
       pocet++;
       p[i][0]=pole[z];
       p[i][1]=pocet;
       i++;
       hodnota=hodnota/pole[z];
    }
    for(int j=0; j<z; j++)
    { 
       if(p[j][0]!=p[j+1][0])
          cout << p[j][0] << "^" << p[j][1] << " * ";
    }
}

int main()
{
  int x=0;
  cout << "Zadej cislo <2-100>: ";
  cin >> x;
  
  Rozklad(x);
  cout << endl;
   
  system("pause");
  return 0;
}

Kondr · 12. 12. 2009 21:21 — Editoval Kondr (08. 12. 2010 14:06)

↑ mobby: Jak jsem psal, ten původní kód má mouchy. Trochu jsem ho opravil:

Code:

void Rozklad(int hodnota)
{
    int pole[PP] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
    int z = 0; //inicialni index prvocisla
    while(hodnota > 1) //postupne delime, dokud nesnizime hodnotu na 1
    {
       while(hodnota%pole[z]!=0) //preskocime prvocisla, ktera hodnotu nedeli
       {
          z++;
       }
       int stupen = 0;
       delitel = z<25 ? pole[z] : hodnota; //pokud musime delit prvocislem mimo pole, je prvocislem sama hodnota
       while(hodnota % delitel == 0) //prvocislem, ktere hodnotu deli, delime dokud lze
       {
                  stupen++;
                  hodnota=hodnota/pole[z];
       }
       cout << pole[z] << "^" << stupen << (hodnota>1?"*":"");   //za poslednim cinitelem nevypisujeme *   
    }
}

zlamal89 · 17. 12. 2009 20:44

Dekuji vsem moc za ochotu a za pomoc. Uz jsem si to dokazal napsat sam a docela lechce, ale bez napadu tady bych to nedokazal

Matematické Fórum

#1 05. 12. 2009 13:27

Rozklad na prvočinitele v C++

#2 05. 12. 2009 13:41 — Editoval gladiator01 (05. 12. 2009 13:43)

Re: Rozklad na prvočinitele v C++

Code:

#3 05. 12. 2009 13:56

Re: Rozklad na prvočinitele v C++

Code:

#4 05. 12. 2009 16:54

Re: Rozklad na prvočinitele v C++

#5 08. 12. 2009 11:14 — Editoval zlamal89 (08. 12. 2009 11:15)

Re: Rozklad na prvočinitele v C++

#6 08. 12. 2009 11:29

Re: Rozklad na prvočinitele v C++

#7 08. 12. 2009 11:39 — Editoval zlamal89 (08. 12. 2009 11:40)

Re: Rozklad na prvočinitele v C++

#8 08. 12. 2009 17:01 — Editoval gladiator01 (08. 12. 2009 20:18)

Re: Rozklad na prvočinitele v C++

Code:

#9 08. 12. 2009 20:13

Re: Rozklad na prvočinitele v C++

#10 08. 12. 2009 20:18 — Editoval gladiator01 (08. 12. 2009 20:22)

Re: Rozklad na prvočinitele v C++

#11 08. 12. 2009 21:02

Re: Rozklad na prvočinitele v C++

#12 08. 12. 2009 21:04

Re: Rozklad na prvočinitele v C++

#13 08. 12. 2009 21:37 — Editoval gladiator01 (08. 12. 2009 21:42)

Re: Rozklad na prvočinitele v C++

Code:

Code:

#14 12. 12. 2009 15:37

Re: Rozklad na prvočinitele v C++

#15 12. 12. 2009 20:21

Re: Rozklad na prvočinitele v C++

Code:

#16 12. 12. 2009 21:21 — Editoval Kondr (08. 12. 2010 14:06)

Re: Rozklad na prvočinitele v C++

Code:

#17 17. 12. 2009 20:44

Re: Rozklad na prvočinitele v C++

Zápatí