Why did this prime factorisation algorithm give the correct answer even though there is a flaw?

The problem stated to me was this:

"What is the largest prime factor of the number 600851475143 ?"

The program is used to find the answer was exactly this using C:

#include<math.h> // for remainder because % does not work with double or floats
#include<stdio.h>  
main()
{
    double x=600851475143,y=3.0;
    while(x!=y)                         // divide until only the number can divide itself
    {
        if(remainder((x/y),1)==0.0)     // if x is divisible by y which means it is a factor then do the magic
        {
            x=x/y;                      // divide the number x by y thereby reducing one constituent factor
        }
        y=y+2;                          // add 2 simply because only odd numbers can be prime and hence only prime numbers can be prime factors
    }
    printf("%lf",y);                    // do the printing magic
}

The question is exactly ask you is that I attempt to check and divide x by all odd numbers, but note that not all odd numbers are not prime numbers, this flaw in the algorithm should cause the answer to be wrong because in reality i should be checking for prime factors (not odd factors).

Surprisingly the answer this program spews out is correct, I checked the answer.

How do I get my head around this? It does not make sense.

Answers


Note there are 3 flaws in the algorithm:

  1. 2 is also a prime number
  2. It might divide numbers that are not prime numbers and odd (like 9)
  3. It does NOT divide prime number more then once (As you would have expected it to do for numbers such as 27).

From these we can conclude that the broken algorithm will yield the correct answer if the 2 following conditions apply:

  1. The input number is odd (so the skipping on 2 does not matter)
  2. Let the number be n = p1*p2*...*p_k where p_i are all prime numbers. For each j!=i : p_i != p_j. In here it means that actually each prime number is a factor of the input number only once, and thus problems 2+3 are "avoided". (Problem 2 - it's trivial why it is avoided, problem 3 is avoided because you already divided the number with all relevant prime factors, so for each m=p_i1*...*p_ic, since the number was already divided by all prime factors - p_i1,...p_ic - you will fail to divide it with m.

Since everybody else is telling you what's wrong with your program, I'll give a correct algorithm for factoring integers using trial division:

function factors(n)
    f, fs := 2, []
    while f * f <= n
        if n % f == 0
            append f to fs
            n := n / f
        else f := f + 1
    append n to fs
    return fs

This solves two problems with your code. First, it properly identifies factors of 2. Second, it returns all factors with their multiplicity.

To answer your question about dividing by non-primes: it's a performance issue, not aa correctness issue. Since the trial divisors are tested in increasing order, any composite divisors will have already been removed from the number being factored when their constituent primes were tested. That means division by a composite is useless, but it won't affect the result.

And of course you should never use floating point arithmetic when working with integers. In C, once you are beyond long long integers, you probably want to switch to the gmp library.

There are better algorithms than trial division for factoring integers, and there are also better ways to implement trial division than shown above. But that makes a good place to start. When you are ready for more, I modestly recommend the essay Programming with Prime Numbers at my blog.


It works because your number does not have repeated factors.

600851475143 = 71 * 839 * 1471 * 6857

Try with, for example, 1573499 (23 * 37 * 43 * 43).


If the number tested is even then the program will run forever. x will always be even, y will always be odd, so x == y will never be true.

If the number tested is an odd prime or the product of distinct odd primes, then the loop will find all prime factors but the last and divide by those prime factors, until only the largest prime factor is left, the loop will exit when y equals that largest prime factor, and the largest prime factor is printed.

The interesting case is when the number tested has factors that are squares, cubes etc. of odd primes. The loop will find odd prime factors and divide by them, but for example if 3^2 is a factor, it will divide by 3 leaving a factor of 3. What exactly happens depends on the prime factors. If there is only one prime square factor p^2, the program will not end. If there is a cube or two squares (p^3 or p^2 q^2), the result will be the wrong left-over factor p^2 or pq, unless the number has a larger prime factor than that.

Example: 3^2 x 5^2 x 13: The factors 3, 5 and 13 are found, then 15 is printed which is wrong. Example: 3^2 x 5^2 x 17: The factors 3, 5 and 15 are found, then 17 is printed which happens to be correct.


Need Your Help

Print content from a vector of a class

c++

I would like to print the content from a vector that is in my class Board

How to append strings using sprintf?

c printf

I am facing a serious issue with sprintf.