Posted By

NerdGnome on 02/19/11


Tagged


Versions (?)

assignment


 / Published in: Pseudocode
 

Background:

For several millennia, since the Greek school of Pythagoras in 500 B.C. in fact, mathematicians have been interested in Prime Numbers. Prime Numbers have once again become a hot topic in recent years because they are the foundation of most encryption algorithms for data security.

By definition: An integer greater than one is called a prime number if its only positive divisors (factors) are one and itself.

It has long been known that there are infinitely many prime numbers (Euclid, 300 B.C.), but another interesting question is how close together are the prime numbers, one from the next. Or, in other words, are there, for example, more or less primes between 1 and 100 than there are between 1001 and 1100? What about 1000001 and 1000100? Does the “density” of prime numbers increase or decrease as the numbers themselves get larger?

At first sight the primes seem to be distributed among the integers in rather a haphazard way. For example in the 100 numbers immediately before 10,000,000 there are 9 primes, while in the 100 numbers after there are only 2 primes. However, on a large scale, the way in which the primes are distributed is very regular. Legendre and Gauss both did extensive calculations of the density of primes. Gauss (who was a prodigious calculator) told a friend that whenever he had a spare 15 minutes he would spend it in counting the primes in a 'chiliad' (a range of 1000 numbers). By the end of his life it is estimated that he had counted all the primes up to about 3 million. Both Legendre and Gauss came to the conclusion that for large n the density of primes near n is about 1/log(n).

For more background on this fascinating subject, see http://www-gap.dcs.st-and.ac.uk/~history/HistTopics/Prime_numbers.html.

Assignment:

Write a C++ program to calculate and display the number of primes in the first 50 “chiliads”. Your results should be exactly as presented below, under testing.

Design Considerations:

I think you will find your program easier to structure and write if you break it down into functions with the following prototypes:

bool isPrime (long n); // Returns true if n is a prime, else false

long primeCount (long x, long y); // Returns the number of primes between x and y, inclusive.

This assignment is primarily an exercise in using heavily nested loops, and decomposing your program into several component functions. So it is a requirement that you use the functional decomposition suggested above, or something quite similar to it.

Deliverables:

Please name your file a05.cpp. Upload your program source code (a05.cpp file) as usual. Be sure to comment your code as required, and to acknowledge any sources of help you may have received. Your header comments should include the identification of the assignment and your name. It should also include a comment indicating any sources of help you may have received. If there were none, the line should read:

// Sources: None.

Points will be awarded for the following attributes of your solution:

a. If your program does not compile, you get only 3 points irrespective of what the error is. b. If it compiles, I check and deduct points for the following: i. Your file name must be a05.cpp ii. Your header section must have “Sources:” line to include any sources you may have used. iii. The quality of your source code (Form). In particular, pay attention to your indentation, capitalization, and so forth. Be sure to read the class C++ style guide before working on this problem. However, if you follow the style used in the book you will be fine! iv. Your program must use functions and loops. c. Program works as specified, and does not have the above mentioned deficits, full points will be awarded.

Testing:

The output of your program should be the following, according to my calculations!

Start End Number of Primes 1 1000 168 1001 2000 135 2001 3000 127 3001 4000 120 4001 5000 119 5001 6000 114 6001 7000 117 7001 8000 107 8001 9000 110 9001 10000 112 … … … 49001 50000 98

Total primes in the first 50 chiliads: 5133 Average number per chiliad: 102.66 Additional Exploration (not to be submitted for grading):

It might be interesting to modify your program to repeat Gauss’ lifetime of calculations. Apparently, he managed to calculate all the prime numbers up to 3 million.

Is your program capable of extending the above table to 3 million? How long does it take to calculate the number of primes in all the chiliads up to 3,000,000? How many such primes are there altogether (up to 3 million)? What is the average number per chiliad in this case?

How far can your program get in 1 hour of processing? I.e. How many chiliads can your program process in one hour? By the way, there is a famous algorithm for enumerating prime numbers. Google for the Sieve of Eratosthenes

  1. Background:
  2.  
  3. For several millennia, since the Greek school of Pythagoras in 500 B.C. in fact, mathematicians have been interested in Prime Numbers. Prime Numbers have once again become a hot topic in recent years because they are the foundation of most encryption algorithms for data security.
  4.  
  5. By definition: An integer greater than one is called a prime number if its only positive divisors (factors) are one and itself.
  6.  
  7. It has long been known that there are infinitely many prime numbers (Euclid, 300 B.C.), but another interesting question is how close together are the prime numbers, one from the next. Or, in other words, are there, for example, more or less primes between 1 and 100 than there are between 1001 and 1100? What about 1000001 and 1000100? Does the “density” of prime numbers increase or decrease as the numbers themselves get larger?
  8.  
  9. At first sight the primes seem to be distributed among the integers in rather a haphazard way. For example in the 100 numbers immediately before 10,000,000 there are 9 primes, while in the 100 numbers after there are only 2 primes. However, on a large scale, the way in which the primes are distributed is very regular. Legendre and Gauss both did extensive calculations of the density of primes. Gauss (who was a prodigious calculator) told a friend that whenever he had a spare 15 minutes he would spend it in counting the primes in a 'chiliad' (a range of 1000 numbers). By the end of his life it is estimated that he had counted all the primes up to about 3 million. Both Legendre and Gauss came to the conclusion that for large n the density of primes near n is about 1/log(n).
  10.  
  11. For more background on this fascinating subject, see http://www-gap.dcs.st-and.ac.uk/~history/HistTopics/Prime_numbers.html.
  12.  
  13. Assignment:
  14.  
  15. Write a C++ program to calculate and display the number of primes in the first 50 “chiliads”. Your results should be exactly as presented below, under testing.
  16.  
  17. Design Considerations:
  18.  
  19. I think you will find your program easier to structure and write if you break it down into functions with the following prototypes:
  20.  
  21. bool isPrime (long n);
  22. // Returns true if n is a prime, else false
  23.  
  24. long primeCount (long x, long y);
  25. // Returns the number of primes between x and y, inclusive.
  26.  
  27. This assignment is primarily an exercise in using heavily nested loops, and decomposing your program into several component functions. So it is a requirement that you use the functional decomposition suggested above, or something quite similar to it.
  28.  
  29. Deliverables:
  30.  
  31. Please name your file a05.cpp. Upload your program source code (a05.cpp file) as usual. Be sure to comment your code as required, and to acknowledge any sources of help you may have received. Your header comments should include the identification of the assignment and your name. It should also include a comment indicating any sources of help you may have received. If there were none, the line should read:
  32.  
  33. // Sources: None.
  34.  
  35. Points will be awarded for the following attributes of your solution:
  36.  
  37. a. If your program does not compile, you get only 3 points irrespective of what the error is.
  38. b. If it compiles, I check and deduct points for the following:
  39. i. Your file name must be a05.cpp
  40. ii. Your header section must have “Sources:” line to include any sources you may have used.
  41. iii. The quality of your source code (Form). In particular, pay attention to your indentation, capitalization, and so forth. Be sure to read the class C++ style guide before working on this problem. However, if you follow the style used in the book you will be fine!
  42. iv. Your program must use functions and loops.
  43. c. Program works as specified, and does not have the above mentioned deficits, full points will be awarded.
  44.  
  45. Testing:
  46.  
  47. The output of your program should be the following, according to my calculations!
  48.  
  49. Start End Number of Primes
  50. 1 1000 168
  51. 1001 2000 135
  52. 2001 3000 127
  53. 3001 4000 120
  54. 4001 5000 119
  55. 5001 6000 114
  56. 6001 7000 117
  57. 7001 8000 107
  58. 8001 9000 110
  59. 9001 10000 112
  60. 49001 50000 98
  61.  
  62. Total primes in the first 50 chiliads: 5133
  63. Average number per chiliad: 102.66
  64. Additional Exploration (not to be submitted for grading):
  65.  
  66. It might be interesting to modify your program to repeat Gauss’ lifetime of calculations. Apparently, he managed to calculate all the prime numbers up to 3 million.
  67.  
  68. Is your program capable of extending the above table to 3 million? How long does it take to calculate the number of primes in all the chiliads up to 3,000,000? How many such primes are there altogether (up to 3 million)? What is the average number per chiliad in this case?
  69.  
  70. How far can your program get in 1 hour of processing? I.e. How many chiliads can your program process in one hour? By the way, there is a famous algorithm for enumerating prime numbers. Google for the Sieve of Eratosthenes

Report this snippet  

You need to login to post a comment.