Assignment 3
(Functions)

Part 1 (Credit: 70%)

Any prime (other than 2) must be of the form 4k+1 or 4k+3. For a positive integer n, let s₁(n) denote the number of primes of the form 4k+1 less than or equal to n, and let s₃(n) denote the number of primes of the form 4k+3 less than or equal to n. In this assignment, you are asked to find out the smallest value of n for which s₁(n) > s₃(n). You may proceed as follows.

• Write a function that accepts a positive integer as input and returns the decision whether the input integer is prime.

• Inside the main() function, keep on checking odd integers 3,5,7,9,... for primality until the condition s₁(n) > s₃(n) is satisfied.

• Print the value of n, s₁(n) and s₃(n) after the loop terminates.

Part 2 (Credit: 30%)

• Modify (append) the main() function of Part 1 such that your program also calculates the number of times the quantity s₁(n) - s₃(n) changes sign for n <= 1,000,000.