Prímfaktorizáció

Fórumok

Sziasztok!

Tudna valaki adni egy működő forráskódot primfaktorizációra? Ami egy adott bemeneti számot primtényezőire bont. előre is köszi!

Hozzászólások


static void pbfft_getprimdivs(int n,int *r)
{
 int k,w;

 while ( n>1 )
  {     if ( n%2==0 )   *r=2,r++,n/=2;
        else            break;
  }

 for ( k=3,w=9 ; n>1 && w<=n ; )
  {     if ( n%k==0 )   *r=k,r++,n=n/k;
        else            w+=4*k+4,k+=2;
  }
 if ( n>1 )             *r=n,r++;
 *r=0;
}

egy elegge primitiv valami; az 'r' tombot feltolti (aminek elegge nagynak kell lennie, azaz 32 bites inteket feltetelezve 32 elemu"nek legalabb) a primtenyezokkel, majd a tombot egy 0-val zarja.

Ha prímenként megengedsz egy ulong helyfoglalást, akkor itt egy O(fi(n)) igényű megoldás.
(Az összes 4 byte-os prímszám kb. 700MB-on fér el, ha az ulong is 4 byte-os :)...)


/* gcc -Wall -O3 -lm -o factor factor.c */
#include <stdio.h>
#include <math.h>

unsigned long *prime;
int p_num, p_alloc;

int
main(int argc, char **argv)
{
  unsigned long n, i, sqrtn;
  int p, j;

  if (argc < 2)
    return printf("%s n\n", argv[0]);

  n = strtoul(argv[1], NULL, 0);
  p_alloc = p_num = 1;
  prime = (unsigned long*)malloc(sizeof(unsigned long));
  prime[0] = 2;

  /* check if n is even */
  for (p = 0; !(n % 2); p++)
    n /= 2;
  if (p)
    printf("2^%d\n", p);

  sqrtn = sqrt(n) + 1;
  for (i = 3; i < sqrtn; i += 2)
    {
      /* check if i is prime */
      for (j = 0; (j < p_num) && !(i % prime[j]); j++)
        ;
      if (j < p_num)
        {
          /* i is prime */
          if (p_num == p_alloc)
            {
              p_alloc <<= 1;
              prime = (unsigned long*)realloc(prime, p_alloc * sizeof(unsigned long));
            }
          prime[p_num++] = i;

          /* check if n is divisible by i */
          for (p = 0; !(n % i); p++)
            n /= i;
          if (p)
            {
              printf("%lu^%d\n", i, p);
              sqrtn = sqrt(n) + 1;
            }
        }
    }
  if (n > 1)
    printf("%lu^1\n", n);
  return 0;
}