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

Print the value of n, s_{1}(n) and s_{3}(n) after the loop terminates.
Part 2 (Credit: 30%)
It is known that as n tends to infinity, the quantity s_{1}(n)  s_{3}(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 s_{1}(n)  s_{3}(n) changes sign for n <= 1,000,000.
Submission site  Lab home  Course home  My home