CS19002 Programming and Data Structures Laboratory Spring 2009, Section 2

## 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 s1(n) denote the number of primes of the form 4k+1 less than or equal to n, and let s3(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 s1(n) > s3(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 s1(n) > s3(n) is satisfied.

• Print the value of n, s1(n) and s3(n) after the loop terminates.

### Part 2 (Credit: 30%)

It is known that as n tends to infinity, the quantity s1(n) - s3(n) changes sign infinitely often.

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

Submission site | Lab home | Course home | My home