Thread: biggest prime factor

There can't be a factor larger than the number divided by 2

What if the number is a prime number - 997, 911, 821, ect...

Originally Posted by Click_here

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?

There are many ways of finding primes (or factors of a number, if you want to see it that way) that do not involve storing all of them in an implementation, like wheel factorization. All the methods I know depend on finding smaller primes first though, because you can use those to speed up the search for bigger primes.

Originally Posted by Click_here

What if the number is a prime number - 997, 911, 821, ect...

That doesn't help you do anything. 1 and the number are trivial factors.

http://im.cprogramming.com/images/misc/quote_icon.png Originally Posted by Click_herehttp://im.cprogramming.com/images/bu...post-right.pngWhat if the number is a prime number - 997, 911, 821, ect...



That doesn't help you do anything. 1 and the number are trivial factors.

I'm not sure what you are saying - Are you saying that you shouldn't consider the actual number as a possibility of being the highest prime factor?

I'm just pointing out that he might be right.

There can't be a factor larger than the number divided by 2

What if the number is a prime number - 997, 911, 821, ect...

What I was saying was that the statement that "there can't be any factor larger than the number divided by 2" was wrong. I then provided examples of numbers where that logic fails. Yes you are correct in saying that you can save a lot of time by skipping the numbers between N/2 and N, but that is not what they were saying.

Wow. a lot of respond.
I don't understand all of your respond, but it was an interesting read.
I took your advices and start from the max instead and decremented it by 2.
Here the new code:

Code:

#include <stdio.h>
int main()
{
    long long big, p, max=100;
    for(p=99; p<=max; p=p-2)
        if((p%3!=0)&&(p%5!=0)&&(p%7!=0)&&(max%p==0))
        {
        break;
        }
        printf("%d \n", p);
    return 0;
}

It give me result for small number, but then i saw something that i did wrong from the beginning.
My prime factor test does not work.

Code:

(p%3!=0)&&(p%5!=0)&&(p%7!=0)

For example: 143=11*13 so it is not a prime, however it would pass my test above.
I decide to google way to find prime(mathematically, not coding). I found a few methods, which hurt my brain while reading it.

I'm not going to ask you guys for a way to find prime(using programming) since i want to figure it out myself. However i think it going to be a while because i have a test to prep for.

See you guys later, when i'm done or have more question.
Thanks

I believe what is meant is that 1 and the number itself, will always be a factor for any number

Yes... But not always a Prime Factor... Every number can be made up by multiplying only prime numbers together (it's "Prime Factors", not to be confused with "Factors") and we are trying to find the highest Prime Factor.

Have a look at this Table of prime factors - Wikipedia, the free encyclopedia

Notice that in some instances, the greatest Prime Factor is the number itself - That is what the confusion was about.

For example: 143=11*13 so it is not a prime, however it would pass my test above.
I decide to google way to find prime(mathematically, not coding). I found a few methods, which hurt my brain while reading it.

Googling a way to find primes mathematically may not really help. There are things like Fermat's little theorem, but that gives wrong answers sometimes.

I wouldn't give up on what you're trying. What you are currently doing is a lot like wheel factorization, which is a kind of sieve for primes; it's just an incomplete implementation.

After you fix the algorithm, here's something that may help: if you give a wheel a number it will find a divisor for you. For primes, it should be the same number you put in, for composites it should be the smallest nontrivial divisor. Keep the divisors for later use, and if you can divide the number to make the problem smaller, eventually you will know all of the divisors of the big number.

This is such an interesting problem - I'd love to see what people have come up with -

Does anyone want to send me their code and I'll send you mine

Originally Posted by Click_here

This is such an interesting problem - I'd love to see what people have come up with -

Does anyone want to send me their code and I'll send you mine

OK... no complaints if you don't have 64 bit integers though.