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