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;
}
Hozzászólások
Factoring large integers: classical and pollard p-1 methods
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 :)...)
köszönöm a gyors segítséget!