# Thread: How to factor a number of 100 characters into prime factors in 1-2 seconds?

1. ## How to factor a number of 100 characters into prime factors in 1-2 seconds?

I have a really long number up to 100 symbols in length. For example:
93286507371999205962977351361478938826658030508392 0591925740371392254317064584855785088915745761
And I need to get this answer from it:
Prime factor of 93286507371999205962977351361478938826658030508392 0591925740371392254317064584855785088915745761 is:
995663^8 x 995669^8
I was able to do this with much lower numbers thanks to Sieve of Eratosthenes and signed long long int:
Code:
```int main(int argc, char *argv[]){
int ch = 0;
signed long long int num;
int div = 2;

while ((ch = scanf("%lli", &num)) == 1)
{
if (num > 0){
printf("Prime factor of %lli is:\n", num);
if (num == 1){
printf("%lli", num);
}
while (num > 1){
int tmp = 0;
long int limit = 1000000;
int prime[limit+1];
int arrprime[tmp];
for(int i = 1; i <= limit; i++){
prime[i] = i;
}
for(int i = 2; i*i <= limit; i++){
if (prime[i] != -1){
for(int j = 2*i; j<= limit; j += i){
prime[j] = -1;
}
}
}
for (int i = 0; i < limit; i++){
if (prime[i] > 0){
arrprime[tmp] = prime[i];
tmp++;
}
}

int power = 0;
for (int i = 1; i < tmp; i++){
while ((num % div) == 0){
num /= div;
power++;
if (num == 1){
break;
}
else{
continue;
}
}
if (power > 0){
printf("%d", div);
if (power > 1){
printf("^%d", power);
}
if (num > 1){
printf(" x ");
}
}
div++;
}
}
printf("\n");
div = 2;
}

else if(num == 0){
return 0;
}
}
}```
But this solution would not work with a big number like in the example (Mainly due to long code processing), so I can't really use the Sieve, nor I can use specialized libraries. So how do I get a prime factor out of a very long number (~100 symbols)?

2. So how do I get a prime factor out of a very long number (~100 symbols)?
In 1 to 2 seconds?
You don't.

3. If you want to numerically deal with the large numbers, then perhaps The GNU MP Bignum Library

4. Here is a link to an online factoring program that also includes source code, that finds the the factors for that large number in a fraction of a second.

Integer factorization calculator

The online factoring program accepts expressions, such as 2^512 - 1.

5. Originally Posted by rcgldr
Here is a link to an online factoring program that also includes source code, that finds the the factors for that large number in a fraction of a second.
Really? Try this:
Code:
`1017803105208811141547706054010446761424659440478753690892748944869985260751624643110487274054409671`
Obviously his extremely simple example number can be factored in a fraction of a second. But that's only because it's factors are small.

EDIT: Even a simple-minded program like the following can factor the given number in a fraction of a second.
Code:
```#include <stdio.h>
#include <stdbool.h>
#include <gmp.h>

int main()
{
const char *num = "932865073719992059629773513614789388266580305083"
"920591925740371392254317064584855785088915745761";
// = 995663^8 * 995669^8

mpz_t n;
mpz_init_set_str(n, num, 10);

unsigned long d = 2;
int cnt = 0;
bool first = true;

while (mpz_cmp_ui(n, 1) != 0)
{
if (mpz_fdiv_ui(n, d) == 0)
{
++cnt;
mpz_fdiv_q_ui(n, n, d);
}
else
{
if (cnt > 0)
{
if (!first) printf(" * ");
else        first = false;
printf("%lu", d);
if (cnt > 1) printf("^%d", cnt);
cnt = 0;
}
d += 1 + (d % 2); // so it counts: 2, 3, 5, 7, 9, ...
}
}

if (cnt > 0)
{
if (!first) printf(" * ");
printf("%lu", d);
if (cnt > 1) printf("^%d", cnt);
}

printf("\n");
mpz_clear(n);

return 0;
}```

6. Originally Posted by john.c
Obviously his extremely simple example number can be factored in a fraction of a second. But that's only because it's factors are small.
If the the factors are all large prime numbers it's going to take quite a while, but for 2^512-1, one of the factors is a 62 digit prime, and that takes a fraction of a second.

7. It's a mathematical problem rather than a programming problem, and certainly rather than a C problem.

An entire industry is based onthe premise that factoring large integer with large prime factors is hard. However an awful lot of research has been done on speeding up the process. I don't follow any of it personally - it's neither my talent nor an area of interest for me. I would imagine that most of the literature is pretty inaccessible to a person with only high school math skills.