What if the number is a prime number - 997, 911, 821, ect...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...There can't be a factor larger than the number divided by 2
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.
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?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.
Yes, but I'm not really sure what I'm saying anymore. There are a lot of primes. I'm just pointing out that he might be right. While you're insistent that N might be the highest prime factor, he is also right that 2 is the least possible prime factor. So if you want to be clever you can eliminate at least 1 + N/2 pointless tests. No matter what you are doing I think.
Originally Posted by wiki on trial division
Last edited by whiteflags; 08-10-2012 at 05:05 AM.
You're still offering confusion, and I'll offer a counter example. The prime factors of 10 are 2 and 5. The square root of 10 is about 3.16, as noted by laserlight. Five is generally considered to be greater than 3.16.
The rule you're thinking of is that, if there is no prime factor less than the square root, then there is also no prime factor exceeding the square root.
Yes, absolutely. That is not what the OP is trying to find however.
I've definitely joined your "3%" on this thread.
I believe what is meant is that 1 and the number itself, will always be a factor for any number. One can't be a prime (by definition), and the fact that the number can be a factor for itself, proves nothing, since that is a truism for any number.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?
Last edited by Adak; 08-10-2012 at 06:26 AM.
I'm just pointing out that he might be right.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.What if the number is a prime number - 997, 911, 821, ect...There can't be a factor larger than the number divided by 2
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:
It give me result for small number, but then i saw something that i did wrong from the beginning.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; }
My prime factor test does not work.
For example: 143=11*13 so it is not a prime, however it would pass my test above.Code:(p%3!=0)&&(p%5!=0)&&(p%7!=0)
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
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.I believe what is meant is that 1 and the number itself, will always be a factor for any number
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.
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.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 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
DealOriginally Posted by Click_here
Oh wait, I erased the example that I wrote, but no matter, I'll write it again
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
Yes, that's why you should be testing using a loop. First test 3 as a factor and add 2 each time through the loop. Exit the loop when you've passed the sqrt of p. That way if p is large enough you'll get to 11 eventually.
What should you do inside the loop? That's been posted several times already - keep dividing p by that factor while it is a factor.
Whatever value of p is left after you've exited the loop is the greatest prime factor of the number you started with.
Last edited by KCfromNC; 08-13-2012 at 09:36 AM. Reason: fix quotes