Exercise 9.3.9. To test whether the number n is a prime, you divide n all the integers 1, 2, 3,... up to a, and see if any of them divides evenly. How large does a have to be in order to guarantee that n really is a prime? (*Hint*) G When testing whether n is prime, by the "brute force" method, as long as n is odd we don't need to divide by even numbers (Why?). This means that you only need to test about half of the numbers up to a-more precisely. we only need to test [a/2] numbers, where [x] means "the next integer larger than r". ([x] is called the ceiling of x.) We can pull the same trick with factors that are divisible by 3. Once we've tested 3 as a factor, we don't need to check 9, 15, 21,... or any other number that is divisible by 3. (Why?) So it seems that this reduces the number of factors that we need to check by about a third, since every third integers are divisible by 3. However, we need to be careful here. We've already ruled out the numbers that are divisible by 2, so the numbers that are divisible by both 2 and 3 have already been ruled out. In other words (using m to denote a positive integer, and using the the notation {} to denote the size of sets): {m ≤a and (2| m or 3 | m)}|= |{m ≤a and 2 | m}| + |{m ≤ a and 3 | m}|-|{m ≤a and 6 | m}|.
Exercise 9.3.9. To test whether the number n is a prime, you divide n all the integers 1, 2, 3,... up to a, and see if any of them divides evenly. How large does a have to be in order to guarantee that n really is a prime? (*Hint*) G When testing whether n is prime, by the "brute force" method, as long as n is odd we don't need to divide by even numbers (Why?). This means that you only need to test about half of the numbers up to a-more precisely. we only need to test [a/2] numbers, where [x] means "the next integer larger than r". ([x] is called the ceiling of x.) We can pull the same trick with factors that are divisible by 3. Once we've tested 3 as a factor, we don't need to check 9, 15, 21,... or any other number that is divisible by 3. (Why?) So it seems that this reduces the number of factors that we need to check by about a third, since every third integers are divisible by 3. However, we need to be careful here. We've already ruled out the numbers that are divisible by 2, so the numbers that are divisible by both 2 and 3 have already been ruled out. In other words (using m to denote a positive integer, and using the the notation {} to denote the size of sets): {m ≤a and (2| m or 3 | m)}|= |{m ≤a and 2 | m}| + |{m ≤ a and 3 | m}|-|{m ≤a and 6 | m}|.
Advanced Engineering Mathematics
10th Edition
ISBN:9780470458365
Author:Erwin Kreyszig
Publisher:Erwin Kreyszig
Chapter2: Second-order Linear Odes
Section: Chapter Questions
Problem 1RQ
Related questions
Question
Please do it to Exercise 9.3.10 and please show step by step and explain
![Exercise 9.3.9. To test whether the number n is a prime, you divide n
all the integers 1,2,3,... up to a, and see if any of them divides evenly.
How large does a have to be in order to guarantee that n really is a prime?
(*Hint*)
When testing whether n is prime, by the "brute force" method, as long
as n is odd we don't need to divide by even numbers (Why?). This means
that you only need to test about half of the numbers up to a-more precisely,
we only need to test [a/2] numbers, where [x] means "the next integer
larger than r". ([x] is called the ceiling of x.)
We can pull the same trick with factors that are divisible by 3. Once
we've tested 3 as a factor, we don't need to check 9, 15, 21,... or any other
number that is divisible by 3. (Why?) So it seems that this reduces the
number of factors that we need to check by about a third, since every third
integers are divisible by 3. However, we need to be careful here. We've
already ruled out the numbers that are divisible by 2, so the numbers that
are divisible by both 2 and 3 have already been ruled out. In other words
(using m to denote a positive integer, and using the the notation {...} to
denote the size of sets):
{m ≤a and (2| m or 3 | m)}|=
|{m ≤a and 2 | m}| + |{m ≤ a and 3 | m}|-|{m ≤a and 6 | m}|.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F892e817a-9b32-4eeb-b8fc-5dd7ffde6479%2F8e569608-317d-4184-b114-14264c4fce92%2Fsb5ezt_processed.png&w=3840&q=75)
Transcribed Image Text:Exercise 9.3.9. To test whether the number n is a prime, you divide n
all the integers 1,2,3,... up to a, and see if any of them divides evenly.
How large does a have to be in order to guarantee that n really is a prime?
(*Hint*)
When testing whether n is prime, by the "brute force" method, as long
as n is odd we don't need to divide by even numbers (Why?). This means
that you only need to test about half of the numbers up to a-more precisely,
we only need to test [a/2] numbers, where [x] means "the next integer
larger than r". ([x] is called the ceiling of x.)
We can pull the same trick with factors that are divisible by 3. Once
we've tested 3 as a factor, we don't need to check 9, 15, 21,... or any other
number that is divisible by 3. (Why?) So it seems that this reduces the
number of factors that we need to check by about a third, since every third
integers are divisible by 3. However, we need to be careful here. We've
already ruled out the numbers that are divisible by 2, so the numbers that
are divisible by both 2 and 3 have already been ruled out. In other words
(using m to denote a positive integer, and using the the notation {...} to
denote the size of sets):
{m ≤a and (2| m or 3 | m)}|=
|{m ≤a and 2 | m}| + |{m ≤ a and 3 | m}|-|{m ≤a and 6 | m}|.
Transcribed Image Text:If we are not so careful with the "ceiling function" (which changes the result
by at most 1 anyway), this tells us:
|{ma and 2 | m or 3 | m}| ~ +
a a a
2 3 6
We can turn this around and find the number of integers which are not
divisible by 2 or 3:
a
a a
+
2
3
¹ (1 - ²) (1 - ² )
5.
{m ≤a and 2 m and 3 m}| ~a-
za
This gives the number of trial divisions required to test whether n is prime.
(Of course we also need to test divisibility by 2 and 3, which are 2 additional
divisions.)
The same reasoning can be extended to take into account divisibility by
5, 7, 11, and so on:
Exercise 9.3.10. Using the same reasoning as above, show that after divid-
ing by 2, 3, 5 the number of additional divisions required to test for primality
is approximately:
a (1 - ¹) (¹ - ¹) (¹ - ¹).
The technique of eliminating numbers to check based on previous divis-
ibility is called the sieve of Eratosthenes.
Expert Solution
Step 1
Step by step
Solved in 2 steps with 2 images
Recommended textbooks for you
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
Numerical Methods for Engineers
Advanced Math
ISBN:
9780073397924
Author:
Steven C. Chapra Dr., Raymond P. Canale
Publisher:
McGraw-Hill Education
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
Numerical Methods for Engineers
Advanced Math
ISBN:
9780073397924
Author:
Steven C. Chapra Dr., Raymond P. Canale
Publisher:
McGraw-Hill Education
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Mathematics For Machine Technology
Advanced Math
ISBN:
9781337798310
Author:
Peterson, John.
Publisher:
Cengage Learning,
