## Question

Accept 2 numbers D - number of hours per day , p- number of parts in a day .(D/P is a natural number)
Equivalent Instances are the simultaneous hours after the day being partitioned into P parts
Equivalent prime instance -An instance with all the hours being prime
Calculate the number of instances of equivalent prime hours.
```
(example :36 3 Instances-{1,13,25}{2,14,26}{3,15,27}...{12,24,36}
Equivalent prime instance-{5,17,29}
```

**Find the complete question here.**

`Solution by Gayatri Ambati`

## Algorithm

Pre calculate seive array to reduce time complexity.

We have n(number of hours per day) and k(number of parts per day).

Find duration of each part

`duration = (number of hours per day)/(number of parts per day)`

Store the first hour value of each partition in an array of length p)

`Ex a[]={1,13,25} for 36 3`

Initialize ans variable to 0. -Now we have first instance of time

- check whether all the hours in present instance are prime. if yes - increment the count of ans. if even one of the hour is not prime - dont consider it as Equivalent prime instance.
- Simultaneously increment each hour in the instance by 1 to get the next instance of day.
- do the same for n/k times. ( As there will be n/k instances per day)
- print the ans being calculated!

## Solution

```
#include <bits/stdc++.h>
using namespace std;
int seive[600];
void SieveOfEratosthenes() //precalculation to answer isprime(n) in O(1)
{
int n=600;
// Create a boolean array "seive[0..n]" and initialize
// all entries it as -1. A value in seive[i] will
// finally be 0 if i is Not a prime, else -1.
memset(seive,-1,sizeof(seive)); // mark all numbers as prime
seive[1]=0; // 1 is not prime so mark it 0
for(int p=2;p*p<=n;p++)
{
if(seive[p]==-1) // If seive[p] is not changed, then it is a prime
{
// Update all multiples of p greater than or
// equal to the square of it
// numbers which are multiple of p and are
// less than p^2 are already been marked.
for(int i=p*p;i<=n;i+=p)
seive[i]=0;
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long int n,k;
cin>>n>>k; //n is the number of hours per day and k is the number of parts per day
SieveOfEratosthenes();//precalculations to answer isprime(n) in O(1)
long int i=0,j,l,m,o,p=n/k; //p- duration of each part
int a[100];
long int n1=n,k1=k,ans=0,flag=0;
n1=1;
while(n1<n)
{
a[i]=n1; //storing the first instance of the day in a[]
n1+=(p);
i++;
}
m=i;
for(i=0;i<p;i++) //checking each equivalent instance if it is Equivalent prime Instance
{
flag=0; // to check if all the hours in instance are prime
for(j=0;j<m;j++)
{
if(seive[a[j]]!=-1)
//even if one hour in instance is not prime,
//that instance can't be Equivalent prime Instance.
{
flag=1; //marking as 1 to represent this instance as not Equivalent prime Instance.
}
a[j]++; //increment every hour to get the next instance of the day.
}
if(flag==0) // if every hour in the instance is prime then add 1 to the answer!!
ans++;
}
cout<<ans; // finally...print the answer!!!!!!!!!!
}
```