CODEWITHSUNDEEP
prime-factoring
Daniel Cortild
Daniel Cortild

Reputation: 203

Getting the prime factorisation of a number rapidly less than 100^100

I want to make a program that can compare the prime factorisation of numbers of the size 100^100. I want the program to tell me if there is an 2, for example, in the prime factorisation, but I don't want to know how many there are... And than I want to compare the prime factorisation of two numbers... Could someone help? The difficulty is really the size of the numbers... And the efficiency of the program... I would like that comparing two numbers only takes like maximum 10 seconds...

I have this;

import java.util.ArrayList;
import java.util.List;

public class PrimeFactorisation {
    public static List<Integer> primeFactors(int numbers) {
            int n = numbers;
            List<Integer> factors = new ArrayList<Integer>();
            for (int i = 2; i <= n / i; i++) {
                    while (n % i == 0) {
                            factors.add(i);
                            n /= i;
                    }
            }
            if (n > 1) {
                    factors.add(n);
            }
            return factors;
    }

    public static void main(String[] args) {
            System.out.println("Primefactors of 44");
            for (Integer integer : primeFactors(12345678901)) {
                    System.out.println(integer);
            }
    }
}

This code is for Java, but I am primarly searching for something efficient, so I am willing to change the language...

Upvotes: 1

Views: 59

Answers (2)

user448810
user448810

Reputation: 17874

In general, you won't be able to find factors of numbers that large. But if you only want to know if two numbers have the same factors except for multiplicity, it's fairly easy. Use Euclid's algorithm to find the greatest common factor of the two numbers. If the result is 1, the numbers are coprime and do not have the same factors. Otherwise, factor the greatest common factor into primes; that should be much easier than factoring the two big numbers, since it will probably be much smaller. Then divide each of the big numbers by each of the common prime factors until it doesn't divide evenly; if, after dividing by all of the common prime factors, the two remainders are the same, you can declare that the two original numbers have the same prime factors but in different multiplicities, otherwise you know that they have prime factors that aren't shared. Ask if you need to know more.

That's a rather odd request. What is your use case? Perhaps there is some other way to solve the underlying problem.

Upvotes: 1

Malcolm McLean
Malcolm McLean

Reputation: 6404

These are huge integers. Using a huge integer library, you will get most of them down to pretty low values quite quickly by tasking out the low factors, but not all of them - primes aren't uncommon.

But you don't need the factors, you need to know if two numbers share a common factor. There is I believe a test for that. It's fairly complicated and a bit beyond my mathematical expertise, but it's a component or randomised primality testing.

Upvotes: 0

Related Questions