Question 387993: What is the greatest prime that must be used to determine if 2089 is a prime?
hannah_janeczak@my.uri.edu
Answer by jsmallt9(3759)   (Show Source):
You can put this solution on YOUR website! To explain the answer, I am going to show you an example. Let's look at the factors of 24:
1 and 24
2 and 12
3 and 8
4 and 6
6 and 4
8 and 3
12 and 2
24 and 2
As you can see there are 8 different factors of 24: 1, 24, 2, 12, 3, 8, 4 and 6. In the list above all eight of these factors appear in the first four pairs. The last four pairs so not add any new factors! So when looking for any and all factors of a number, we only have to look at the "first half" of the list of factors. We just have to know where the "first half" ends. For 24 we can see that the "first half" ends somewhere between 4 and 6. The "first half" of the list for 24 ends at  .
So for 2089 the "first half" ends at  which is approximately 45.7. To determine if 2089 is prime, we must test all prime numbers that are less than or equal to 45.7. Since 45 and 44 are not prime, 43 is the highest prime number you need to test. If you test all prime numbers up to 43 and none of them are factors of 2089 then 2089 is prime.
| |
|
