Problem Name: Praveen and Subsequence

Contest Link: CodeChef: Practical coding for everyone

Difficulty: EASY

Contest Code: PAR

Prerequisites: AD-HOC

Problem: Praveen went on a date with his girlfriend.He gave her a sequence of numbers from 1 to 1000000. Praveen picked up a subsequence from it and wants his girlfriend to pick a number from that subsequences. What is the probability that the number she picked was a prime number?

Explanation:

The range of the subsequence chosen by Praveen is given which is L and R.

So in this range first we will have to calculate the number of prime numbers.

To calculate the number of prime numbers in a given range the most efficient algorithm is Sieve of Eratosthenes

Now as we have the count of prime numbers , we just have to divide the number of prime numbers present in the range and total numbers in the given range as we can get the probability of choosing a prime number

That can be done by obtaining the total number by :- R-L+1

And dividing the total count of prime numbers by the total numbers:

Probability of finding the

a prime number is ⇒ ( float ) count of prime numbers/ sum