Problems with primes

Question

I am trying to write a program to find the largest simple coefficient of a very large number, and have tried several methods with varying degrees of success. Everything I've found so far has been incredibly slow. I had a thought and I wonder if this is really a valid approach:

long number = input; while(notPrime(number)) { number = number / getLowestDivisiblePrimeNumber(); } return number; 

This approach will require input and will do the following:

200 → 100 → 50 → 25 → 5 (return)

90 → 45 → 15 → 5 (return)

It repeatedly divides currentNum with the smallest divisible number (most often 2 or 3) until currentNum itself becomes prime (there is no divisible prime less than the square of the current Num) and assumes that this is the largest simple coefficient the original input.

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

-

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

Answer 1

This will always work due to the unique theoretical theory of factorization .

Answer 2

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

• Less than 2 ^ 16 or so: Search table.
• Less than 2 ^ 70 or so: Atkin Sieve . This is an optimized version of the more famous Sieve of Eratosthenes . Edit: A modification of Richard Brent's Pollard-Roff algorithm might be better in this case.
• Less than 10 ^ 50: Fragmentation of an elliptic Lenstra curve
• Less than 10 ^ 100: Quadratic strainer
• Over 10 ^ 100: General field sieve with numbers

Answer 3

Of course, this will work (see Mark Bayer's answer ), but for "very large" inputs this can take too long. You should notice that your call to getLowestDivisiblePrimeNumber() hides another loop, so it works in O (N ^ 2) and that depending on what you mean by "very large", you may have to work on BigNums , which will be slow .

You can speed it up a bit by noticing that your algorithm should never check for factors less than those found.

Answer 4

You are trying to find the main factors of the number. What you offer will work, but will still be slow for large numbers ... you should be thankful for this, since most modern security tools are based on the fact that this is a complex problem.

Answer 5

From the quick search I just made, the fastest way to determine the number is to use the elliptic curve method.

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

If this convinces you, you can either try to steal the code (which is not funny, they provide a link to it!), Or read the theory of it elsewhere. There is a Wikipedia article here: http://en.wikipedia.org/wiki/Lenstra_elliptic_curve_factorization , but I'm too dumb to figure it out. Fortunately, this is your problem, not mine! :)

Answer 6

The thing with Project Euler is that there is usually an obvious brute force method to solve this problem, which will almost always take. As matters get more complicated, you will need to implement smart solutions.

One way to solve this problem is to use a loop that always finds the smallest (positive integer) coefficient of a number. When the smallest coefficient of a number is a number, then you have found the largest primary coefficient!

Detailed description of the algorithm:

You can do this by storing three variables:

The number you are trying to determine (A) The current divisor repository (B) The largest divisor repository (C)

Initially, let (A) be the number of interest to you - in this case it is 600851475143. Then let (B) be 2. You have a condition that checks whether (A) is divisible by (B). If it is divisible, divide (A) by (B), reset (B) by 2 and return to check if (A) is divisible by (B). Otherwise, 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) becomes 1. Your returned (3) will be the largest prime divisor 600851475143.

There are many ways to make this more efficient - instead of incrementing to the next integer, you can increment to the next necessarily prime integer, and instead of storing the largest divisor storage, you can simply return the current number when it's only the divisor itself by oneself. However, the above algorithm will execute in seconds independently.

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: find the largest simple coefficient 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. An increment of (B) by +1: (B) = 3. 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, (A) is divisible by (B)? No. An increment of (B) by +1: (B) = 3. Is (A) divisible by (B)? No. An increment of (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 earlier is stored in (C). (C) currently 3. 5 is greater 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 continue to increase (B) until (B) = (A), since 7 is simple and has no divisors other than itself and 1. (We already could stop when (B)> ((A) / 2), since you cannot have numeric divisors greater than half the number - the smallest possible divisor (except 1) of any number is 2!)

So, at this point we return (A) = 7.

Try to make a few of them manually, and you will understand the idea