Exercise 6 - Sieve of Eratosthenes (Finding All Prime Numbers within a range) Eratosthenes of Cyrene...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Exercise 6 - Sieve of Eratosthenes (Finding All Prime Numbers within a range) Eratosthenes of Cyrene lived approximately 275-195 BC. He was the first to accurately estimate the diameter of the earth. For several decades he served as the director and chief librarian of the famous library in Alexandria. He was highly regarded in the ancient world, but unfortunately only fragments of his writing have survived. The algorithm described for this assignment is known as the Sieve of Eratosthenes. The algorithm is designed to find all prime numbers within a given range in an interesting way - instead of testing each number to see if it is prime, it assumes that all numbers are prime. It then finds all "non prime" numbers and marks them as such. When the algorithm is finished you are left with a list of numbers along with their designation (Prime or Not Prime). How does the algorithm work? Begin by selecting a range of numbers to test - our goal is to examine these numbers and determine which numbers in this range are prime. Your lowest number will be 0 and your highest number will be n. Create a list of n+1 values where n is the highest number you want to test. Populate each element in this list with the String P for "Prime" since we initially will assume that all numbers in our range are prime. For example, if you were testing all numbers between 0 and 10 your list would look like the following: 0 1 2 3 4 5 6 7 8 9 10 P P P P P P P P P P P Next, we need to indicate that our "special case" numbers - 0 and 1 - are not prime. To do this simply switch the values of elements 0 and 1 to 'N' for "Not Prime". Your list should look like this: 0 1 2 3 4 5 6 7 8 9 10 N N P P P P P P P P P Next, we will move onto our first "non-special" number, 2. The value at position 2 in the list is currently 'P' meaning that 2 is a prime number. Our job now is to mark every MULTIPLE of 2 equal to 'N' for "Not Prime" since any number evenly divisible by 2 cannot possibly be prime. So we can set up some kind of looping structure to visit all multiples of 2 and set them equal to 'N' for "Not Prime". Your list should look like this after this operation: 0 1 2 3 4 5 6 7 8 9 10 N N P P N P N P N P N 'P' Now we move onto our next number, 3. The value at position 3 in the list is listed as | meaning we need to mark all multiples of 3 equal to 'N' for "Not Prime". Note that the number 6 was already visited in a previous iteration of your program so there is really nothing to do here it was already marked as "Not Prime" so you can safely move onto the next number and not make any changes to it. Your list should look like this after this operation: 0 1 2 3 4 5 6 7 8 9 10 N N P P N P N P N N N Next we move onto the number 4. Number 4 is marked as "Not Prime", so there is nothing to do here. We can skip it and move right onto the next number to test. The value at position 5 in the list is listed as 'P' meaning we need to mark all mul- tiples of 5 equal to "N" for "Not Prime". Your list should look like this after this operation: 0 1 2 3 4 5 6 7 8 9 10 N N P P N P N P N N N Next we move onto the number 6. But really, there is no need to even examine this number since all of its multiples are beyond the end of our maximum range. So we can effectively stop the program at this point and examine all numbers in our list. Any number that has been marked with a 'P is a Prime number! Here is your task: Ask the user for a positive integer greater than or equal to 10. Ensure the value is positive - if it is not, re-prompt the user. This number will be referred to as n. Create a list of n + 1 values... all of which are set to 'P (hint: use list repetition). This list represents the numbers 0 to n. (based on the indexes in the list) Set your "known" non-prime numbers (positions 0 and 1) to "N" for "Not Prime". Set up some kind of loop that examines all numbers from 2 through n. -If the value stored at the position you are examining is holding the value 'P' for "Prime" then you need to visit all positions that are multiples of that number and set those the value at those positions equal to N for "Not Prime". (you will probably need another loop to do this) -If the value stored at the position you are examining is holding the value "N" for "Not Prime" then you can effectively skip it and move onto the next number. When you are finished examining all numbers your program should print out all of the prime numbers that you have found in neatly aligned columns (with up to 10 prime numbers on every row). Notes on Efficiency: Efficiency is important here - here are some hints: If an item in your list has already been set to "what does this tell you about the multiples of that item's index? Do you even need to visit them? and should be replaced by True and False . Certain numbers do not need to be tested. Say you are testing all numbers between 0 and 1000 and you get to the number 800. This number cannot have any multiples less than or equal to 1000. Generalize this idea to make your program much more efficient. Exercise 6 - Sieve of Eratosthenes (Finding All Prime Numbers within a range) Eratosthenes of Cyrene lived approximately 275-195 BC. He was the first to accurately estimate the diameter of the earth. For several decades he served as the director and chief librarian of the famous library in Alexandria. He was highly regarded in the ancient world, but unfortunately only fragments of his writing have survived. The algorithm described for this assignment is known as the Sieve of Eratosthenes. The algorithm is designed to find all prime numbers within a given range in an interesting way - instead of testing each number to see if it is prime, it assumes that all numbers are prime. It then finds all "non prime" numbers and marks them as such. When the algorithm is finished you are left with a list of numbers along with their designation (Prime or Not Prime). How does the algorithm work? Begin by selecting a range of numbers to test - our goal is to examine these numbers and determine which numbers in this range are prime. Your lowest number will be 0 and your highest number will be n. Create a list of n+1 values where n is the highest number you want to test. Populate each element in this list with the String P for "Prime" since we initially will assume that all numbers in our range are prime. For example, if you were testing all numbers between 0 and 10 your list would look like the following: 0 1 2 3 4 5 6 7 8 9 10 P P P P P P P P P P P Next, we need to indicate that our "special case" numbers - 0 and 1 - are not prime. To do this simply switch the values of elements 0 and 1 to 'N' for "Not Prime". Your list should look like this: 0 1 2 3 4 5 6 7 8 9 10 N N P P P P P P P P P Next, we will move onto our first "non-special" number, 2. The value at position 2 in the list is currently 'P' meaning that 2 is a prime number. Our job now is to mark every MULTIPLE of 2 equal to 'N' for "Not Prime" since any number evenly divisible by 2 cannot possibly be prime. So we can set up some kind of looping structure to visit all multiples of 2 and set them equal to 'N' for "Not Prime". Your list should look like this after this operation: 0 1 2 3 4 5 6 7 8 9 10 N N P P N P N P N P N 'P' Now we move onto our next number, 3. The value at position 3 in the list is listed as | meaning we need to mark all multiples of 3 equal to 'N' for "Not Prime". Note that the number 6 was already visited in a previous iteration of your program so there is really nothing to do here it was already marked as "Not Prime" so you can safely move onto the next number and not make any changes to it. Your list should look like this after this operation: 0 1 2 3 4 5 6 7 8 9 10 N N P P N P N P N N N Next we move onto the number 4. Number 4 is marked as "Not Prime", so there is nothing to do here. We can skip it and move right onto the next number to test. The value at position 5 in the list is listed as 'P' meaning we need to mark all mul- tiples of 5 equal to "N" for "Not Prime". Your list should look like this after this operation: 0 1 2 3 4 5 6 7 8 9 10 N N P P N P N P N N N Next we move onto the number 6. But really, there is no need to even examine this number since all of its multiples are beyond the end of our maximum range. So we can effectively stop the program at this point and examine all numbers in our list. Any number that has been marked with a 'P is a Prime number! Here is your task: Ask the user for a positive integer greater than or equal to 10. Ensure the value is positive - if it is not, re-prompt the user. This number will be referred to as n. Create a list of n + 1 values... all of which are set to 'P (hint: use list repetition). This list represents the numbers 0 to n. (based on the indexes in the list) Set your "known" non-prime numbers (positions 0 and 1) to "N" for "Not Prime". Set up some kind of loop that examines all numbers from 2 through n. -If the value stored at the position you are examining is holding the value 'P' for "Prime" then you need to visit all positions that are multiples of that number and set those the value at those positions equal to N for "Not Prime". (you will probably need another loop to do this) -If the value stored at the position you are examining is holding the value "N" for "Not Prime" then you can effectively skip it and move onto the next number. When you are finished examining all numbers your program should print out all of the prime numbers that you have found in neatly aligned columns (with up to 10 prime numbers on every row). Notes on Efficiency: Efficiency is important here - here are some hints: If an item in your list has already been set to "what does this tell you about the multiples of that item's index? Do you even need to visit them? and should be replaced by True and False . Certain numbers do not need to be tested. Say you are testing all numbers between 0 and 1000 and you get to the number 800. This number cannot have any multiples less than or equal to 1000. Generalize this idea to make your program much more efficient.
Expert Answer:
Related Book For
Posted Date:
Students also viewed these algorithms questions
-
From the attached article: 1) Introduction - Describe the case. What happened? When did that happen? Who got involved? 2) Identify the link between the case and global market changes?...
-
Note: All ML code must be explained clearly (INJAVAXX)and should be free of needless complexity. 2 CST.2016.1.3 2 Foundations of Computer Science Please help. (2c) (a) A prime number sieve is an...
-
In Exercises 1 through 14, compute the indicated values of the given function. f(x) = 3x 2 + 5x 2; f(0), f(2), f(1)
-
Is it inevitable that employees will respond to change with feelings of fear? If you believe the answer is yes, state the implications of this for managing strategic change. If you believe the answer...
-
Over the three-year period presented in Exhibit 1, Bickchips return on equity is best described as: A. stable. B. trending lower. C. trending higher. Quentin Abay, CFA, is an analyst for a private...
-
Public sector organizations increasingly must account for their performance and provide quality services at lower costs. To accomplish this many local authorities and public sector organizations have...
-
Kenton and Denton Universities offer executive training courses to corporate clients. Kenton pays its instructors $5,000 per course taught. Denton pays its instructors $250 per student enrolled in...
-
Your company has identified $2750 per week of potential savings on your processing line. Your company wishes to deposit these savings into an account that earns 1.15% interest compounded weekly....
-
We take 6 pairs of siblings and we measure their IQ. We get the following data: First born kid: 130, 118, 132, 100, 140, 145 . Second born kid: 110, 120, 118, 106, 122, 119 where we list siblings in...
-
Regardless of what number you calculated for Scott's 2023-equivalent rent payment, assume $12,000/ month. Given this, what annual interest rate is needed to get from their $300/mo. in 1923 to...
-
What is the output of the following code: int num = 10; double temp = 4.5; bool found; found = (num == 2* static_cast (temp + 1)); cout < < "The value of found is : " < < found;
-
Discuss the relationship between the 3 multilevel systems of organizational learning. What should organizations do to facilitate learning at each level?
-
What are examples of forensic document examination comparisons?
-
Last year Katie purchased a 9% corporate bond for its par value of $1,000. This year Katie received coupon payments totaling $90. What is the tax consequence for Katie this year, and what is her cost...
-
Identify the following types of reactions as precipitation, acid/base neutralization or oxidation reduction a. HBr (aq) + KOH (aq) H 2 O (l) + KCl(aq) b. Pb(NO 3 ) (aq) + KCl (aq) PbBr 2 (s) + KNO...
-
Doorharmony Company makes doorbells. It has a weighted- average cost of capital of 5% and total assets of $ 5,900,000. Doorharmony has current liabilities of $ 750,000. Its operating income for the...
-
Twitter is trading at \($34.50.\) Call options with a strike price of \($35\) are priced at \($2.30\) . What is the intrinsic value of the option, and what is the time value?
-
Name five variables that can affect the price of options, and briefly explain how each affects prices. How important are intrinsic value and time value to in-the-money options? To out-of-the-money...
-
Consider the following statements about a futures clearinghouse: Statement 1: A clearinghouse in futures contracts allows for the offsetting of contracts prior to delivery. Statement 2: A...
Study smarter with the SolutionInn App