Problem 4. (While loop and boolean variables: TestingPrimality) A positive integ

Question

Problem 4. (While loop and boolean variables: TestingPrimality) A positive integer n is called a prime number if it is notequal to 1 and if the only positive integers which divide n are 1 and n. For instance: 2,3,5,7,11,13,. .. a) (Testing Primality) Write a computer program which given aninteger, outputs a message indi- cating whether the number is prime. Hint: Declare a boolean variable isPrime initialized to true.Check the integers 2, 3, . . . , n 1 starting from 2 and update the variable isPrime if neededafter suitable considerations. At the end print the desired message depending on the value of theboolean variable isPrime. b) (A smarter test) Do you have to check all the integers 2, 3, . . . , n1?(argue that it is enough to check if n is divisible by an integer d between 2 and n (inclusive).) Do you have to continue your search for a divisor of n if youhave found one? Inspired by the above two observations, write a more efficientversion of your program in Part (a). (Note: It is worth mentioning that this problem has puzzledpeople since ancient times. The idea underlying the test in Part (b) was discovered before 200 BC.The most efficient test known today was discovered only 8 years ago, and people are still lookingfor faster primality tests ...). c) (Density of Primes) Write a program which given a positiveinteger x, computes the fraction f(x) of prime numbers less than or equal to x, i.e., thenumber of prime numbers less than or equal to x divided by x. d) (Optional) Guess the asymptotic behavior of 1/f(x) as xgrows. (This goes back to the 18’th century ...). Problem 4. (While loop and boolean variables: TestingPrimality) A positive integer n is called a prime number if it is notequal to 1 and if the only positive integers which divide n are 1 and n. For instance: 2,3,5,7,11,13,. .. a) (Testing Primality) Write a computer program which given aninteger, outputs a message indi- cating whether the number is prime. Hint: Declare a boolean variable isPrime initialized to true.Check the integers 2, 3, . . . , n 1 starting from 2 and update the variable isPrime if neededafter suitable considerations. At the end print the desired message depending on the value of theboolean variable isPrime. b) (A smarter test) Do you have to check all the integers 2, 3, . . . , n1?(argue that it is enough to check if n is divisible by an integer d between 2 and n (inclusive).) Do you have to continue your search for a divisor of n if youhave found one? Inspired by the above two observations, write a more efficientversion of your program in Part (a). (Note: It is worth mentioning that this problem has puzzledpeople since ancient times. The idea underlying the test in Part (b) was discovered before 200 BC.The most efficient test known today was discovered only 8 years ago, and people are still lookingfor faster primality tests ...). c) (Density of Primes) Write a program which given a positiveinteger x, computes the fraction f(x) of prime numbers less than or equal to x, i.e., thenumber of prime numbers less than or equal to x divided by x. d) (Optional) Guess the asymptotic behavior of 1/f(x) as xgrows. (This goes back to the 18’th century ...).

Explanation / Answer

please rate - thanks sorry about that, I wasn't paying attention CRAMSTER rule - 1 question per post I will do part c which has the answer to the others in it #include #include using namespace std; int main() { int j,n,max,total=0; bool isPrime; coutmax; for(n=2;n

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.