Prime Time Again
You have been given two integers ‘DAY_HOURS’ and ‘PARTS’. Where ‘DAY_HOURS’ is the number of hours in a day and a day can be divided into ‘PARTS’ equal parts. Your task is to find total instances of equivalent prime groups. Prime group refers to the group of elements (hours) which are prime and measure the same equivalent time since the start of the day.

For example, if we consider ‘DAY_HOURS’ to be 24 and ‘PARTS’ to be 2, then the day of total 24 hours is divided into 2 parts ( 1 - 12 ) and ( 13 - 24 ). 5 hours in the first part of the day is equivalent to 17, which is 5 hours into the second part of the day. And since 5 and 17 both are prime, they can be considered as a prime group.

Note:

1. Day starts with hour 1 and ends with hour ‘DAY_HOURS’. 2. Each hour of the prime group should be in a different part of the day. 3. If there is no prime group then return zero. 4. ‘DAY_HOURS’ should be divisible by ‘PARTS’, meaning that the number of hours per part (DAY_HOURS/PARTS) should be a natural number.

Example:

Let ‘DAY_HOURS’ = 20 and ‘PARTS’ = 2 Hence the view of our day would be in the following format: 1 2 3 4 5 6 7 8 9 10 - Part 1 11 12 13 14 15 16 17 18 19 20 - Part 2 1-11 Not a prime group because 1 is not prime. 2-12 Not a prime group because 12 is not prime. 3-13 Because both 3 and 13 are prime, it is an equivalent prime group. 4-14 Not a prime group because 4 and 14 are not prime. 5-15 Not a prime group because 15 is not prime. 6-16 Not a prime group, because 6 and 16 are not prime. 7-17 Because both 7 and 17 are prime, it is an equivalent prime group. 8-18 Not a prime group, because 8 and 18 are, is not prime. 9-19 Not a prime group because 9 is not prime. 10-20 Not a prime group because both 10 and 20 are not prime. Hence there are 2 equivalent prime groups in the above format which are 3-13 and 7-17.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases. The first and the only line of each test case contains two space-separated integers ‘DAY_HOURS’ and ‘PARTS’.

Output Format

The output for each test case contains a single integer denoting the number of instances of equivalent prime groups. The output of each test case will be printed in a separate line.

Note

You are not required to print the output, it has already been taken care of. Just implement the function.

Constraints:

1

Question

Prime Time Again

You have been given two integers ‘DAY_HOURS’ and ‘PARTS’. Where ‘DAY_HOURS’ is the number of hours in a day and a day can be divided into ‘PARTS’ equal parts. Your task is to find total instances of equivalent prime groups. Prime group refers to the group of elements (hours) which are prime and measure the same equivalent time since the start of the day.

For example, if we consider ‘DAY_HOURS’ to be 24 and ‘PARTS’ to be 2, then the day of total 24 hours is divided into 2 parts ( 1 - 12 ) and ( 13 - 24 ). 5 hours in the first part of the day is equivalent to 17, which is 5 hours into the second part of the day. And since 5 and 17 both are prime, they can be considered as a prime group.

Note:

1. Day starts with hour 1 and ends with hour  ‘DAY_HOURS’.

2. Each hour of the prime group should be in a different part of the day.

3. If there is no prime group then return zero.

4. ‘DAY_HOURS’ should be divisible by ‘PARTS’, meaning that the number of hours per part (DAY_HOURS/PARTS)  should be a natural number.

Example:

Let ‘DAY_HOURS’ = 20  and ‘PARTS’ = 2

Hence the view of our day would be in the following format: 

1  2  3  4  5  6  7  8  9 10      -  Part 1
11 12 13 14 15 16 17 18 19 20     -  Part 2

 1-11  Not a prime group because 1 is not prime.
 2-12  Not a prime group because 12 is not prime.
 3-13  Because both 3 and 13 are prime, it is an equivalent prime group.
 4-14  Not a prime group because 4 and 14 are not prime.
 5-15  Not a prime group because 15 is not prime.
 6-16  Not a prime group, because 6 and 16 are not prime.
 7-17  Because both 7 and 17 are prime, it is an equivalent prime group.
 8-18  Not a prime group, because 8 and 18 are, is not prime.
 9-19  Not a prime group because 9 is not prime.
 10-20 Not a prime group because both 10 and 20 are not prime.

 Hence there are 2 equivalent prime groups in the above format which are 3-13 and 7-17.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first and the only line of each test case contains two space-separated integers ‘DAY_HOURS’ and ‘PARTS’.

Output Format

The output for each test case contains a single integer denoting the number of instances of equivalent prime groups.

The output of each test case will be printed in a separate line.

Note

You are not required to print the output, it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 100
10 <= DAY_HOURS <= 5 * 10^3
2 <= PARTS <= 10^3

Time Limit: 1 second

Accepted Answer

Brute Force

This is a Naive/Brute Force approach
Create a 2-d array of size ‘P’ rows and ‘D/P’ columns and assign 1 to ‘D’ value in each cell.
Take an example with ‘D’ being 12 and ‘P’ being 2, then create an array [ [1,2,3,4,5,6] [7,8,9,10,11,12] ]
Keep track of the number of prime group instances using a ‘PRIME_GROUP’ variable, which would be initialized to 0.
We can easily observe that each column in the array represents the same equivalent group of hours.
Do column level traversal, which means we will be traversing through all the equivalent hours and check if all elements of the column prime or not .
If equivalent group is prime group then increase the count of ‘PRIME_GROUP’

Space Complexity: O(1)Explanation:

O(D), Where ‘D’ is the number of hours in a day.

Space required to create an array of size P rows and (D/P) columns.

Time Complexity: O(1)Explanation:

O(D^2), Where ‘D’ is the number of hours in a day.

In this approach, we are iterate rows from 0 to P-1 and for every row, we iterate col from 0 to D/P-1 and for every number, at ARR[ROW][COL] we are checking is prime or not.

Total time complexity is P*(D/P)*D = D^2, Where an order of ‘D’ time is required to check number is prime or not

Accepted Answer

Using the equation

This is the space optimization method of Approach 1
Each hour which we used to store in ARR[ROW][COL] in the previous method can be calculated by the equation ‘ROW*(D/P)+col+1’.
Suppose ‘D’ is 20 and ‘P’ is 2, hence the division would be as follows: [ [1,2,3,4,5,6,7,8,9,10],[11,12,13,14,15,16,17,19,20] ] ARR[0][0]=1 for this, row number is 0 and col number is 0, can find with ‘ROW*(D/P)+COL+1’ = 0*(20/2)+0+1 = 1 and ARR[1][2]=13 for this ROW number is 1 and COL number is 2 , can find with ‘ROW*(D/P)+COL+1’ = 1* (20/2)+2+1= 13
Hence we can iterate the col from 0 to D/P -1 because there is a total D/P number of hours in a single part of the day.
For each row, we can do column level traversal and iterate from 0 to P-1 which would contain a group of all equivalent hours in the Day. While doing column level traversal and check if all elements of the column are prime or not
In each iteration keep track of the count of total equivalent prime groups

Space Complexity: O(1)Explanation:

O(1), We are using constant space

Time Complexity: O(n^2)Explanation:

O(D^2), Where ‘D’ is the number of hours in a day.

In this approach, we are iterate row from 0 to P-1 and for each row, we iterate col from 0 to D/P-1 and every position at ‘ROW*(D/P)+COL+1’ we checking if the hour/element is prime or not

Total Time complexity P*(D/P)*D=D^2, Where an order of last ‘D’ time is required to check number is prime or not

Accepted Answer

Optimal Approach

This is the optimization of Approach 2
Create a list of size 5001 and assign all values True
Call it ‘PRIME_ARR’ to keep track of number ‘i’ is prime or not
Initially, Let ‘K’ equals 2, which is the first prime number.
Iterate from ‘K’^2 to 5001
If ‘PRIME_ARR[K]’ is True then all the multiples of of ‘K’ will be non-prime
Hence assign all multiples of ‘K’ to non-prime with ‘PRIME_ARR[X]’=False, Where ‘X’ is multiple of ‘K’.
Then increase the value of ‘K’ by 1 and repeat step 5
Hence, in each test case, while iterating through the hours, no need to find whether the number/hour is prime or not.

Space Complexity: O(1)Explanation:

O(5001) ~ O(1),

We need to create only a 5001 sized i.e. ‘K’ sized array for pre-computation of the numbers/hours because the value of ‘D’ can be at max 5000.

Time Complexity: O(1)Explanation:

O(5000) ~ O(1),

We can find whether the number is prime or not in constant time with pre-computation which depends majorly on the number of hours in the day ‘D’ which could grow up to 5 * 10^3 therefore, the time complexity here becomes O(1).

Note:

Example:

Input format:

Output Format

Note

Constraints:

Popular interview questions of Assistant System Engineer