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

  1. #1
    Registered User
    Join Date
    Jan 2021
    Posts
    1

    Question 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)?
    Last edited by owlyboi; 01-04-2021 at 05:57 PM.

  2. #2
    Registered User
    Join Date
    Dec 2017
    Posts
    1,127
    So how do I get a prime factor out of a very long number (~100 symbols)?
    In 1 to 2 seconds?
    You don't.
    The best argument against democracy is a five minute conversation with the average voter. - Churchill

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,658
    If you want to numerically deal with the large numbers, then perhaps The GNU MP Bignum Library
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  4. #4
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    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.
    Last edited by rcgldr; 01-06-2021 at 01:48 PM.

  5. #5
    Registered User
    Join Date
    Dec 2017
    Posts
    1,127
    Quote Originally Posted by rcgldr View Post
    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;
    }
    Last edited by john.c; 01-06-2021 at 02:39 PM.
    The best argument against democracy is a five minute conversation with the average voter. - Churchill

  6. #6
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    Quote Originally Posted by john.c View Post
    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. #7
    Registered User
    Join Date
    May 2012
    Posts
    502
    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.
    I'm the author of MiniBasic: How to write a script interpreter and Basic Algorithms
    Visit my website for lots of associated C programming resources.
    https://github.com/MalcolmMcLean


Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Find Prime Factors Of Given NUmber
    By san12345 in forum C Programming
    Replies: 2
    Last Post: 12-03-2015, 02:35 AM
  2. Finding The Biggest Prime Factor Of a Number
    By thedardwhie in forum C Programming
    Replies: 9
    Last Post: 02-11-2015, 12:58 PM
  3. help with prime factor for 12 digit number
    By nick2 in forum C Programming
    Replies: 15
    Last Post: 06-19-2009, 04:39 AM
  4. Calculating prime factor of a huge number.
    By Bakster in forum C Programming
    Replies: 15
    Last Post: 02-20-2009, 12:06 PM
  5. Replies: 3
    Last Post: 03-29-2005, 04:24 PM

Tags for this Thread