Prvočíselný rozklad na součet dělitelů – Matematika – Fórum – Programujte.com

Zdravím,

už nad tím přemýšlím docela dlouho a zatím mě nenapadlo jak z prvočíselného rozkladu určit součet všech dělitelů čísla. Vím, že je spolu musím nějak vynásobit, atp. Například pro číslo 20 - prvočíselný rozklad je 2*2*5 a já z toho potřebuji dostat součet dělitelů, čili: 1+2+4+5+10=22. Za každý nápad díky

Opravdu nevíte? Moc by mi to pomohlo...

Tady jsem zbastlil kód který ti třeba pomůže, ale rychlost nic moc :-)

(Princip je asi takový, že se postupně k součtu rekurzivně přičítají všechny kombinace prvků rozkladu)

#include <stdio.h>
#include <assert.h>
#include <string.h>

#define DELKA_ROZKLADU (sizeof(prvociselnyRozklad) / sizeof(prvociselnyRozklad[0]))

int prvociselnyRozklad[] = {2, 2, 5}; // Cisla v rozkladu musi byt serazena vzestupne

struct BLOCK {  
  int* mocniny;
  int  powCount;
};

BLOCK blocks[DELKA_ROZKLADU];
int   blocksCount = 0;

void InitBlocks();
void PrintBlocks();
int RecursiveSum(int start, int mul); // Pozor: hloubka rekurze = pocet mocnin v rozkladu + 1 (např pro 2^4 * 5 je hloubka = 3)

int main(int argc, char* argv[])
{  
  int slozeneCislo = 1;
  for (int j = 0; j < DELKA_ROZKLADU; j++) {
    slozeneCislo *= prvociselnyRozklad[j];
  }

  InitBlocks(); // Prevede jednotlive prvky v rozkladu na mocniny (napr 2, 2, 2, 3, 3, 5 na 2^3, 3^2, 5)
  PrintBlocks();

  int sum = 1 + RecursiveSum(0, 1) - slozeneCislo;

  printf("Soucet delitelu: %d\n", sum);
	return 0;
}

void InitBlocks()
{
  blocksCount = 0;
  blocks[blocksCount].powCount = 1;
  blocks[blocksCount].mocniny = prvociselnyRozklad;
  int j = 1;
  while (j < DELKA_ROZKLADU) {
    if (prvociselnyRozklad[j] != blocks[blocksCount].mocniny[0]) {
      blocksCount++;
      blocks[blocksCount].powCount = 1;  
      blocks[blocksCount].mocniny = prvociselnyRozklad + j;
    } else {
      prvociselnyRozklad[j] *= prvociselnyRozklad[j - 1];
      blocks[blocksCount].powCount++;  
    }   
    j++;
  }
  blocksCount++;
}

void PrintBlocks()
{
  for (int j = 0; j < blocksCount; j++) {
    if (blocks[j].powCount == 1) {
      printf("%d", blocks[j].mocniny[0]);
    } else {
      printf("%d^%d", blocks[j].mocniny[0], blocks[j].powCount);
    }
    if (j < blocksCount - 1) {
      printf(" * ");
    }
  }
  printf("\n");
}

int RecursiveSum(int start, int mul) 
{
  int sum = 0;
  for (int blockIndex = start; blockIndex < blocksCount; blockIndex++) {
    for (int powIndex = 0; powIndex < blocks[blockIndex].powCount; powIndex++) {
      const int m = mul * blocks[blockIndex].mocniny[powIndex];
      sum += m + RecursiveSum(blockIndex + 1, m);
    }
  }  
  return sum;
}

#3 Pudni tvor
ok, díky za pomoc, ale objevil jsem toto, což mi dost pomohlo: http://primes.utm.edu/glossary/page.php?sort=SigmaFunction