Problems with prime numbers

Question

I am trying to write a program to find the largest prime factor of a very large number, and have tried several methods with varying success. All of the ones I have found so far have been unbelievably slow. I had a thought, and am wondering if this is a valid approach:

long number = input;

while(notPrime(number))
{
    number = number / getLowestDivisiblePrimeNumber();
}

return number;

This approach would take an input, and would do the following:

200 -> 100 -> 50 -> 25 -> 5 (return)

90 -> 45 -> 15 -> 5 (return)

It divides currentNum repeatedly by the smallest divisible number (most often 2, or 3) until currentNum itself is prime (there is no divisible prime number less than the squareroot of currentNum), and assumes this is the largest prime factor of the original input.

Will this always work? If not, can someone give me a counterexample?

-

EDIT: By very large, I mean about 2^40, or 10^11.

Rosalinarosalind

I'd like to see the implementation of your magical notPrime() function. :) – Desperation

heh, that's easy: notPrime(n) = (getLowestDivisiblePrimeNumber(n) == n) . – Albigenses

To be honest, I use while(true) there, it was just easier to explain this way. My getLowestDivisiblePrime method refers to an ArrayList<Long> primeList; If there is no divisible prime number in primeList, it finds the next prime number to add to primeList, and continues doing so until it either finds a prime that 'number' is divisble by (and will later refer to a larger list of primes), or until the largest prime in primeList is greater than the sqaureroot of 'number'. No magic there, though I do hope it to be fairly efficient. =P – Rosalinarosalind

21 : 10 5 2 whereas 7 should be yielded. Bad luck. – Ellga

Answer 1

This will always work because of the Unique Prime Factorization Theorem.

Tournai

For corner cases, 0 and 1 are neither prime nor composite, and given that long is signed, you'll need to figure out how you want to handle negative numbers. – Punt

Answer 2

The method will work, but will be slow. "How big are your numbers?" determines the method to use:

• Less than 2^16 or so: Lookup table.
• Less than 2^70 or so: Sieve of Atkin. This is an optimized version of the more well known Sieve of Eratosthenes. Edit: Richard Brent's modification of Pollard's rho algorithm may be better in this case.
• Less than 10^50: Lenstra elliptic curve factorization
• Less than 10^100: Quadratic Sieve
• More than 10^100: General Number Field Sieve

Enrichment

I'm impressed by your references to algorithms I've never heard of, but: Are not these algorithms much better suited for finding all prime numbers up to a given limit, than for factoring a single number? – Albigenses

I agree with Carl. While I cannot state this as fact (I have not studied on the above mentioned methods), I believe this to be a very effecient method for finding the largest prime factor. How I implement notPrime() -or rather, !prime()- is another matter entirely. – Rosalinarosalind

@Jonathan: How big is "very large"? – Enrichment

That falls under "quite small" - easy to factor in milliseconds. Go with Richard Brent's algorithm. – Enrichment

Of the listed algorithms, only the Sieve of Eratosthenes and Sieve of Atkin actually attempt to calculate large lists of primes. Pollard's rho, Lenstra's ECM, the Quadratic and General Number Field Sieves are all exclusively factoring algorithms. And they're all asymptotically "slow". Though none is nearly so bad as trial division (the questioner's algorithm) – Montfort

@280Z28 Nice table, but 10^20 < 2^70. – Inly

Answer 3

Certainly it will work (see Mark Byers' answer), but for "very large" inputs it may take far too long. You should note that your call to getLowestDivisiblePrimeNumber() conceals another loop, so this runs at O(N^2), and that depending on what you mean by "very large" it may have to work on BigNums which will be slow.

You could speed it up a little, by noting that your algorithm need never check factors smaller than the last one found.

Astromancy

Though to be picky, it does say 'long' and uses 'Java' in the question tag, so that's only 2**63 and not a BigNum sort of problem. On the other hand, documentation lies. :) – Punt

@dalke: Ack. Seeing the words "very large" kinda stuck me in a rut. And I think the improved version can run in (kinda slow) linear time, though the method the OP suggests will use a lot of space... – Astromancy

Answer 4

You are trying to find the prime factors of a number. What you are proposing will work, but will still be slow for large numbers.... you should be thankful for this, since most modern security is predicated on this being a difficult problem.

Topping

Answer 5

From a quick search I just did, the fastest known way to factor a number is by using the Elliptic Curve Method.

You could try throwing your number at this demo: http://www.alpertron.com.ar/ECM.HTM .

If that convinces you, you could try either stealing the code (that's no fun, they provide a link to it!) or reading up on the theory of it elsewhere. There's a Wikipedia article about it here: http://en.wikipedia.org/wiki/Lenstra_elliptic_curve_factorization but I'm too stupid to understand it. Thankfully, it's your problem, not mine! :)

Albigenses

Answer 6

The thing with Project Euler is that there is usually an obvious brute-force method to do the problem, which will take just about forever. As the questions become more difficult, you will need to implement clever solutions.

One way you can solve this problem is to use a loop that always finds the smallest (positive integer) factor of a number. When the smallest factor of a number is that number, then you've found the greatest prime factor!

Detailed Algorithm description:

You can do this by keeping three variables:

The number you are trying to factor (A) A current divisor store (B) A largest divisor store (C)

Initially, let (A) be the number you are interested in - in this case, it is 600851475143. Then let (B) be 2. Have a conditional that checks if (A) is divisible by (B). If it is divisible, divide (A) by (B), reset (B) to 2, and go back to checking if (A) is divisible by (B). Else, if (A) is not divisible by (B), increment (B) by +1 and then check if (A) is divisible by (B). Run the loop until (A) is 1. The (3) you return will be the largest prime divisor of 600851475143.

There are numerous ways you could make this more effective - instead of incrementing to the next integer, you could increment to the next necessarily prime integer, and instead of keeping a largest divisor store, you could just return the current number when its only divisor is itself. However, the algorithm I described above will run in seconds regardless.

The implementation in python is as follows:-

def lpf(x):
        lpf = 2;
        while (x > lpf):
                if (x%lpf==0):
                        x = x/lpf
                        lpf = 2
                else:
                        lpf+=1;
        print("Largest Prime Factor: %d" % (lpf));

def main():
        x = long(raw_input("Input long int:"))
        lpf(x);
        return 0;

if __name__ == '__main__':
    main()

Example: Let's find the largest prime factor of 105 using the method described above.

Let (A) = 105. (B) = 2 (we always start with 2), and we don't have a value for (C) yet.

Is (A) divisible by (B)? No. Increment (B) by +1: (B) = 3. Is Is (A) divisible by (B)? Yes. (105/3 = 35). The largest divisor found so far is 3. Let (C) = 3. Update (A) = 35. Reset (B) = 2.

Now, is (A) divisible by (B)? No. Increment (B) by +1: (B) = 3. Is (A) divisible by (B)? No. Increment (B) by +1: (B) = 4. Is (A) divisible by (B)? No. Increment (B) by +1: (B) = 5. Is (A) divisible by (B)? Yes. (35/5 = 7). The largest divisor we found previously is stored in (C). (C) is currently 3. 5 is larger than 3, so we update (C) = 5. We update (A)=7. We reset (B)=2.

Then we repeat the process for (A), but we will just keep incrementing (B) until (B)=(A), because 7 is prime and has no divisors other than itself and 1. (We could already stop when (B)>((A)/2), as you cannot have integer divisors greater than half of a number - the smallest possible divisor (other than 1) of any number is 2!)

So at that point we return (A) = 7.

Try doing a few of these by hand, and you'll get the hang of the idea

Liquorice