Algorithm to find all the primes less than or equal to n

Assignment Help Basic Computer Science

Reference no: EM131305062

The Sieve of Eratosthenes is an elegant algorithm for finding all of the prime numbers up to some limit n. The basic idea is to first create a list of numbers from 2 to n. The first number is removed from the list, and announced as a prime number, and all multiples of this number up to n are removed from the list. This process continues until the list is empty.

For example, if we wished to find all the primes up to 10, the list would originally contain 2, 3, 4, 5, 6, 7, 8, 9, 10. The 2 is removed and announced to be prime. Then 4, 6, 8, and 10 are removed, since they are multiples of 2. That leaves 3, 5, 7, 9. Repeating the process, 3 is announced as prime and removed, and 9 is removed because it is a multiple of 3. That leaves 5 and 7. The algorithm continues by announcing that 5 is prime and removing it from the list. Finally, 7 is announced and removed, and we're done.

Write a program that prompts a user for n and then uses the sieve algorithm to find all the primes less than or equal to n.

Reference no: EM131305062

Questions Cloud

Write and test a function removeduplicates : Write and test a function removeDuplicates(somelist) that removes duplicate values from a list.

Will it have less money available to lend : How would increasing loan loss reserves reduce the risk of bankruptcy for a smaller bank?- If a bank increases its loan loss reserves, will it have less money available to lend?

Calculate npv and irr for project-reject pineapple project : Hawaiian Coconut Milkshakes Inc. is considering the following project. They would like to expand and add a pineapple branch. The firm has paid $95,000 to a consultant in order to find out more about the available projects and possibilities. Calculate..

What is first nationals roe now : Suppose First National's equity capital declines to $10 million, while its assets and ROA are unchanged. What is First National's ROE now?

Algorithm to find all the primes less than or equal to n : The first number is removed from the list, and announced as a prime number, and all multiples of this number up to n are removed from the list. This process continues until the list is empty.

Explanation of a bank experiencing rising total profits : An article in the Wall Street Journal states that Royal Bank of Canada's ROE.- What is the most likely explanation of a bank experiencing rising total profits and a falling ROE?

.how is production planned from customer demand : Customer demand and process capacity relationships.How is production planned, from customer demand to production schedules?Quality Management issues.Product delivery issues.The interfaces of the process with both the external and internal customers.

Would you become an investor in the bank : You learn that the bank has $300 million in capital and $5 billion in assets. Would you become an investor in this bank? Briefly explain.

Identify two weaknesses target has in comparison to walmart : Identify 1-2 weaknesses Target has in comparison to Walmart. For each weakness, explain your rationale in 2-3 sentences. Identify 1-2 strengths Target has in comparison to Walmart.

User Account

All Pages