biggest prime factor

**robinnbastar** · 08-09-2012

This is my second post. Hi everyone.
ok so i started doing problem number 3 on project euler and meet another obstacle.
Here the problem:

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

Here my code:

Code:

#include<stdio.h>
int main()
{
    long long biggest=0, prime, max=600851475143;
    for(prime=1; prime<=max; prime++)
    {
        if (max%prime==0)
        {
            if ( (prime%2!=0) && (prime%3!=0) && (prime%5!=0) && (prime%7!=0) )
                {
                    biggest= (biggest>prime) ? biggest : prime;
                }
        }        
    }
    printf ("%d", biggest);
    return 0;
}

When i run the .exe file it do nothing, which mean something is running to infinite and didnt exit the loop. but i did set the loop to stop when prime got larger then max.
Did i do something else wrong? I look for the error in loop for 3 hours now and still couldnt find what went wrong.

Thought process:
_find factor using "max%prime==0"
_find prime factor using "(prime%2!=0) && (prime%3!=0) && (prime%5!=0) && (prime%7!=0)"
_compare biggest with prime. "biggest= (biggest>prime) ? biggest : prime;"

Thanks,

**whiteflags** · 08-09-2012

If it were me I would make a tree of factors, a binary tree. The primes will be at the leaf level. Just collect them and find the biggest one.

**Matticus** · 08-09-2012

How long are you waiting before you give up and terminate the program? Because that's quite a large number you're using.

**stahta01** · 08-09-2012

I suggest trying to solve for 13195 before you try the larger number.

Edit:

I tested my logic with 29, 8, and 13195 before I did 600851475143.

It took less than 1 second to get the result.

Hint: I added a second loop around your for loop and completely changed the inner if statement logic.

Tim S.

**robinnbastar** · 08-09-2012

Originally Posted by whiteflags

If it were me I would make a tree of factors, a binary tree. The primes will be at the leaf level. Just collect them and find the biggest one.

I just start programming so i'm not sure what a binary tree is. I'll look into it, maybe i can understand it. thanks

To Matticus and Stahta01: I'll try and leave the terminal work longer and see what happen, cause when i use 13195 like stahta01 said it actually work. I'll report back after awhile.
P.S: reply on this forum are so fast. you guys are awesome.

**stahta01** · 08-09-2012

I rewrote your code two different ways; but, my changes basically boiled down to one very important line. Where I changed the value of max.

I also changed more code to make it more likely to get the right answer with greater likelihood. I was not certain whether the other changes were needed or not.

Tim S.

**Adak** · 08-09-2012

You're working on the mod primality test algorithm.

Some suggestions:

1 is never a prime, by fiat. 2 IS prime, for every even number. You don't need to test any even number - skip them by incrementing the number to be tested, by 2, instead of just by one. (Not prime++, but prime+=2).

Max value you should search for is the square root of 600851475143. Do this ONCE, and that's your real max (but add one to it). Now you're ready for prime<max, instead of the slower prime<=max. There are NO primes for a number > the square root of that number. (some are equal to it, however).

Since you are looking for the GREATEST prime for this number, you may want to start your search with the square root of the 600851475143 number, and work DOWN, instead of UP. First prime you find will be the greatest one, that way.

**laserlight** · 08-09-2012

Originally Posted by Adak

There are NO primes for a number > the square root of that number. (some are equal to it, however).

Counterexample: the square root of 10 is about 3.16. 10 = 2 * 5. 5 is prime. 5 > 3.16. Therefore, there exists a composite number for which a prime factor of that number is greater than that number's square root.

**Adak** · 08-09-2012

Originally Posted by laserlight

Counterexample: the square root of 10 is about 3.16. 10 = 2 * 5. 5 is prime. 5 > 3.16. Therefore, there exists a composite number for which a prime factor of that number is greater than that number's square root.

Yes. That was mis-stated. There are no prime *factors* of a number, greater than the square root of the number - but that's not what you're doing here. Sorry for the confusion.

I'd still suggest if you *must* use the repeating mod test for primality, that you start with the huge max number, and work your way downward, instead of upward, to find the greatest prime number less than the max number. With such a large max number, that is bound to save a boatload of work.

Or better yet, switch over to the Sieve of Eratosthenes. It is not difficult, and WAY faster than this repeating mod test algorithm. Wikipedia has a fine article on it. It mentions still faster algorithms, but I've tried a few of them, and they are NOT faster, on either of my PC's. (both Intel i7's).

**oogabooga** · 08-09-2012

Originally Posted by laserlight

Counterexample: the square root of 10 is about 3.16. 10 = 2 * 5. 5 is prime. 5 > 3.16. Therefore, there exists a composite number for which a prime factor of that number is greater than that number's square root.

He's right if the number is a perfect square. In such a number all the prime factors must occur an even number of times. The least number of times they could each appear is two. Consider:
p1^2 * p2^2 * ... (p1,p2,... are primes and ^ means exponentiation)
The square root of this number is
p1 * p2 * ...
Clearly it is not possible for any pn to be greater than the whole! Increasing the exponents only worsens this problem. So a perfect square has no prime factors greater than it's square root. QED

**oogabooga** · 08-09-2012

Originally Posted by Adak

I'd still suggest if you *must* use the repeating mod test for primality, that you start with the huge max number, and work your way downward, instead of upward, to find the greatest prime number less than the max number. With such a large max number, that is bound to save a boatload of work.

Or better yet, switch over to the Sieve of Eratosthenes. It is not difficult, and WAY faster than this repeating mod test algorithm. Wikipedia has a fine article on it. It mentions still faster algorithms, but I've tried a few of them, and they are NOT faster, on either of my PC's. (both Intel i7's).

You don't need to start at the biggest and work down, and the sieve is probably not a good idea since (as I understand it) it needs a lot of memory.

The trick is to simply divide out the factors as you find them.

Code:

while (number % factor == 0)
    number /= factor;

My little program using that trick can factorize in under a second a number thousands of times bigger than the 600billion+ number given. (And that's on a 32-bit machine.)

**laserlight** · 08-09-2012

Originally Posted by Adak

Yes. That was mis-stated. There are no prime *factors* of a number, greater than the square root of the number - but that's not what you're doing here. Sorry for the confusion.

Hmm... but you're still stating the same incorrect thing, just using more precise language. I think that what you had in mind is the fact that every composite number has a prime factor that is not greater than its square root.

Originally Posted by Adak

I'd still suggest if you *must* use the repeating mod test for primality, that you start with the huge max number, and work your way downward, instead of upward, to find the greatest prime number less than the max number. With such a large max number, that is bound to save a boatload of work.

I agree.

Originally Posted by oogabooga

He's right if the number is a perfect square. (...) So a perfect square has no prime factors greater than it's square root. QED

The input to the algorithm is not guaranteed to be perfect squares, so you have only proven a statement that was irrelevant to begin with (and which I did not dispute).

Originally Posted by oogabooga

The trick is to simply divide out the factors as you find them.

Yeah, that is the idea that I had in mind too. It is basically a variant of whiteflags's suggestion, except that the tree is implicit and you discard prime factors that are not the largest as you go.

**oogabooga** · 08-10-2012

Originally Posted by laserlight

The input to the algorithm is not guaranteed to be perfect squares, so you have only proven a statement that was irrelevant to begin with (and which I did not dispute).

I should have tagged that post "irrelevant but interesting".

Originally Posted by laserlight

Yeah, that is the idea that I had in mind too. It is basically a variant of whiteflags's suggestion, except that the tree is implicit and you discard prime factors that are not the largest as you go.

The other important thing is to test if the number is a factor of max before testing for primality since the primality test is another loop.

Then your worst case is if max is a huge prime, when the outer loop must go from 3 to floor(sqrt(max)) by 2's, which is floor(sqrt(max))/2-1 reps. The sqrt of a 64 bit number is 32 bits so it can't be more than 4 billion (unsigned) which is 2 billion reps, or just 1 billion with signed.

**Click_here** · 08-10-2012

I was interested in this, so I gave it a go.

Basically, I found it faster to try every number (from 2) then to search for the next prime (even though the theory guarantees that the next number found will be a prime). When the number was found, do the divide, and then start from 2 again.

My Intel calculated the prime factors for 600851475143 in 0.016 sec.

I suppose that it would be faster if you only tried primes, but you'd need to have all of them in an array up to (and including) the value of the number you were testing (consider 997, 911, 821, ect...). This isn't impossible, because you have an upper limit to the number you can test - It's just VERY impractical.

Another thing that I found was that the last prime number found always seemed to be the largest - Can anyone confirm my observation?

**erupter** · 08-10-2012

I may point out that there is a rilevancy to the "square root thingy", just that there is no root.
There can't be a factor larger than the number divided by 2, just because 2 is the smallest factor hence whatever is on the other side of the multiplication, is nearer the largest factor.
IE: max = (number / 2) - 1
Then you can work your way downward.
Also if you want full factorization you could use just a "long biggestfactor(long num)" recursive function that calls itself until it gets to the smallest.
But to save data this way you should be proficient with arrays (or lists or trees or whatever) and pointers to avoid losing data in the inner recursions.

Thread: biggest prime factor

Thread Tools

Search Thread

Display

biggest prime factor

Similar Threads

Largest Prime Factor

Prime factor

last prime factor

Prime factor

Prime Factor Fxn