## 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;
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=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;
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++;
}