|CS19002 Programming and Data Structures Laboratory
||Spring 2009, Section 2
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.
Submission site | Lab home | Course home | My home
- 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.