[go: up one dir, main page]
Scribd
Upload
2 views4 pages

CPP Homework 06 20221028

The document outlines homework assignments involving prime numbers, greatest common divisors, and a guessing game. It includes tasks such as writing functions to determine prime numbers and their counts, calculating the GCD of two integers, and creating a number guessing game. The document provides examples and explanations for each task, including performance improvements in prime number calculations.

Uploaded by

n941210
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
2 views4 pages

CPP Homework 06 20221028

The document outlines homework assignments involving prime numbers, greatest common divisors, and a guessing game. It includes tasks such as writing functions to determine prime numbers and their counts, calculating the GCD of two integers, and creating a number guessing game. The document provides examples and explanations for each task, including performance improvements in prime number calculations.

Uploaded by

n941210
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

Homework #6

5.29 (Prime Numbers) An integer is said to be prime if it’s divisible by only 1 and
itself. For example,
2, 3, 5 and 7 are prime, but 4, 6, 8 and 9 are not.
a) Write a function that determines whether a number is prime.
b) Use this function in a program that determines and prints all the prime numbers
between
2 and 10,000. How many of these numbers do you really have to test before being
sure that you’ve found all the primes?
c) Initially, you might think that n/2 is the upper limit for which you must test to see
whether a number is prime, but you need only go as high as the square root of n.
Why?
Rewrite the program, and run it both ways. Estimate the performance improvement.
ANS: If a number n has two factors a and b, then one must be less than the square

root of
n and one must be greater. Therefore, if n is not prime it will have at least one factor
less than the square root of n, and we only need to check that far. The performance
improvement is roughly a factor of ten, though the running times are so small they
are difficult to measure.

The prime numbers from 1 to 10000 are:

2 3 5 7 11 13 17 19 23 29

31 37 41 43 47 53 59 61 67 71

73 79 83 89 97 101 103 107 109 113

127 131 137 139 149 151 157 163 167 173

179 181 191 193 197 199 211 223 227 229

233 239 241 251 257 263 269 271 277 281

283 293 307 311 313 317 331 337 347 349

353 359 367 373 379 383 389 397 401 409

419 421 431 433 439 443 449 457 461 463

...

9739 9743 9749 9767 9769 9781 9787 9791 9803 9811

9817 9829 9833 9839 9851 9857 9859 9871 9883 9887

9901 9907 9923 9929 9931 9941 9949 9967 9973

Total of 1229 prime numbers between 1 and 10000.


5.31 (Greatest Common Divisor) The greatest common divisor (GCD) of two
integers is the largest
integer that evenly divides each of the numbers. Write a function gcd that returns the
greatest common
divisor of two integers.
// int gcd( int, int ); // function prototype
Enter two integers: 6 8

The greatest common divisor of 6 and 8 is 2

Enter two integers: 789 4

The greatest common divisor of 789 and 4 is 1

Enter two integers: 9999 27

The greatest common divisor of 9999 and 27 is 9

Enter two integers: 73652 8

The greatest common divisor of 73652 and 8 is 4

Enter two integers: 99 11

The greatest common divisor of 99 and 11 is 11


5.34 (Guess-the-Number Game) Write a program that plays the game of “guess
the number” as
follows: Your program chooses the number to be guessed by selecting an integer at
random in the
range 1 to 1000. The program then displays the following:
I have a number between 1 and 1000.

Can you guess my number?

Please type your first guess.

? 500

Too high. Try again.

? 250

Too low. Try again.

? 375

Too low. Try again.

? 438

Too high. Try again.

? 405

Too high. Try again.

? 380

Too low. Try again.

? 393

Too low. Try again.

? 399

Too high. Try again.

? 396

Too low. Try again.

? 398

Too high. Try again.

? 397

Excellent! You guessed the number!

Would you like to play again (y or n)? n

You might also like