Given an integer N denoting the number of dices, the task is to find the probability of the product of numbers appearing on the top faces of N thrown dices being a prime number. All N dices must be thrown simultaneously.
Examples:
Input: N = 2
Output: 6 / 36
Explanation:
On throwing N(=2) dices simultaneously, the possible outcomes on the top faces of N(=2) dices having product equal to a prime number are: {(1, 2), (1, 3), (1, 5), (2, 1), (3, 1), (5, 1)}.
Therefore, the count of favourable outcomes = 6 and the count of the sample space is = 36
Therefore, the required output is (6 / 36)Input: N = 3
Output: 9 / 216
Naive Approach: The simplest approach to solve this problem is to generate all possible outcomes on the top faces of N dices by throwing N dices simultaneously and for each possible outcome check if the product of numbers on the top faces is a prime number or not. If found to be true then increment the counter. Finally, print the probability of getting the product of numbers on the top faces as a prime number.
Time Complexity: O(6N * N)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach the idea is to use the fact that the product of N number is a prime number only if (N – 1) numbers are 1 and a remaining number is a prime number. Following are the observations:
If the product of N numbers is a prime number then the value of (N – 1) numbers must be 1 and the remaining number must be a prime number.
Total count of prime numbers in the range [1, 6] is 3.
Therefore, the total number of outcomes in which the product of N numbers on the top faces as a prime number = 3 * N.
P(E) = N(E) / N(S)
P(E) = probability of getting the product of numbers on the top faces of N dices as a prime number.
N(E) = total count of favourable outcomes = 3 * N
N(S) = total number of events in the sample space = 6N
Follow the steps below to solve this problem:
- Initialize a variable, say N_E to store the count of favorable outcomes.
- Initialize a variable, say N_S to store the count of sample space.
- Update N_E = 3 * N.
- Update N_S = 6N.
- Finally, print the value of (N_E / N_S).
Below is the implementation of the above approach
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the value // of power(X, N)long long int power(long long int x, long long int N){ // Stores the value // of (X ^ N) long long int res = 1; // Calculate the value of // power(x, N) while (N > 0) { // If N is odd if(N & 1) { //Update res res = (res * x); } //Update x x = (x * x); //Update N N = N >> 1; } return res;}// Function to find the probability of// obtaining a prime number as the// product of N thrown dices void probablityPrimeprod(long long int N) { // Stores count of favorable outcomes long long int N_E = 3 * N; // Stores count of sample space long long int N_S = power(6, N); // Print the required probability cout<<N_E<<" / "<<N_S;}// Driver codeint main(){ long long int N = 2; probablityPrimeprod(N);} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{ // Function to find the value // of power(X, N)static int power(int x, int N){ // Stores the value // of (X ^ N) int res = 1; // Calculate the value of // power(x, N) while (N > 0) { // If N is odd if (N % 2 == 1) { // Update res res = (res * x); } // Update x x = (x * x); // Update N N = N >> 1; } return res;}// Function to find the probability of// obtaining a prime number as the// product of N thrown dices static void probablityPrimeprod(int N) { // Stores count of favorable outcomes int N_E = 3 * N; // Stores count of sample space int N_S = power(6, N); // Print the required probability System.out.print(N_E + " / " + N_S);}// Driver codepublic static void main(String[] args){ int N = 2; probablityPrimeprod(N);}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program to implement# the above approach# Function to find the value# of power(X, N)def power(x, N): # Stores the value # of (X ^ N) res = 1 # Calculate the value of # power(x, N) while (N > 0): # If N is odd if (N % 2 == 1): # Update res res = (res * x) # Update x x = (x * x) # Update N N = N >> 1 return res# Function to find the probability of# obtaining a prime number as the# product of N thrown dicesdef probablityPrimeprod(N): # Stores count of favorable outcomes N_E = 3 * N # Stores count of sample space N_S = power(6, N) # Print required probability print(N_E, " / ", N_S)# Driver codeif __name__ == '__main__': N = 2 probablityPrimeprod(N)# This code is contributed by 29AjayKumar |
C#
// C# program to implement// the above approachusing System;class GFG{ // Function to find the // value of power(X, N)static int power(int x, int N){ // Stores the value // of (X ^ N) int res = 1; // Calculate the value // of power(x, N) while (N > 0) { // If N is odd if (N % 2 == 1) { // Update res res = (res * x); } // Update x x = (x * x); // Update N N = N >> 1; } return res;}// Function to find the probability // of obtaining a prime number as // the product of N thrown dices static void probablityPrimeprod(int N) { // Stores count of favorable // outcomes int N_E = 3 * N; // Stores count of sample // space int N_S = power(6, N); // Print the required // probability Console.Write(N_E + " / " + N_S);}// Driver codepublic static void Main(String[] args){ int N = 2; probablityPrimeprod(N);}}// This code is contributed by Princi Singh |
Javascript
<script>// JavaScript program to implement the above approach// Function to find the value // of power(X, N)function power(x, N){ // Stores the value // of (X ^ N) let res = 1; // Calculate the value of // power(x, N) while (N > 0) { // If N is odd if (N % 2 == 1) { // Update res res = (res * x); } // Update x x = (x * x); // Update N N = N >> 1; } return res;}// Function to find the probability of// obtaining a prime number as the// product of N thrown dices function probablityPrimeprod(N) { // Stores count of favorable outcomes let N_E = 3 * N; // Stores count of sample space let N_S = power(6, N); // Print the required probability document.write(N_E + " / " + N_S);}// Driver Code let N = 2; probablityPrimeprod(N); // This code is contributed by susmitakunndugoaldanga.</script> |
6 / 36
Time Complexity: O(log2N)
Auxiliary Space: O( 1 )
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
