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!!!!!!!!!!
}