-
Notifications
You must be signed in to change notification settings - Fork 0
/
Prime_Time_Again.cpp
101 lines (78 loc) · 2.11 KB
/
Prime_Time_Again.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
/*
1. Prime Time Again
Here on earth, our 24-hour day is composed of two parts, each of 12 hours. Each hour in each part has a corresponding hour in the other part separated by 12 hours: the hour essentially measures the duration since the start of the day part. For example, 1 hour in the first part of the day is equivalent to 13, which is 1 hour into the second part of the day.
Now, consider the equivalent hours that are both prime numbers. We have 3 such instances for a 24-hour 2-part day:
5 ~ 17
7 ~ 19
11 ~ 23
Accept two natural numbers D, P >1 corresponding respectively to number of hours per day and number of parts in a day separated by a space. D should be divisible by P, meaning that the number of hours per part (D/P) should be a natural number. Calculate the number of instances of equivalent prime hours. Output zero if there is no such instance. Note that we require each equivalent hour in each part in a day to be a prime number.
Example:
Input:
24 2
Output:
3 (We have 3 instances of equivalent prime hours: 5 ~ 17, 7 ~ 19 and 11 ~ 23.)
Constraints
10 <= D < 500
2 <= P < 50
Input
Single line consists of two space separated integers, D and P corresponding to number of. hours per day and number of parts in a day respectively
Output
Output must be a single number, corresponding to the number of instances of equivalent prime number, as described above
Example 1
Input
36 3
Output
2
Explanation
In the given test case D = 36 and P = 3
Duration of each day part = 12
2 ~ 14 ~ X
3 ~ 15 ~ X
5 ~ 17 ~ 29 - instance of equivalent prime hours
7 ~ 19 ~ 31 - instance of equivalent prime hours
11 ~ 23 ~ X
Hence the answers is 2.
*/
#include<bits/stdc++.h>
using namespace std;
bool isprime(int n)
{
if(n==1)
return false;
for(int i=2;i<=(int)sqrt(n);i++)
{
if(n%i==0)
return false;
}
return true;
}
int main()
{
int D,P,i,j,p,t=1;
cin>>D>>P;
p=D/P;
int time[p][P];
for(i=0;i<P;i++)
{
for(j=0;j<p;j++)
{
time[j][i]=t++;
}
}
t=0;
for(i=0;i<p;i++)
{
bool flag=true;
for(j=0;j<P;j++)
{
if(!isprime(time[i][j]))
{
flag=false;
break;
}
}
if(flag)
t++;
}
cout<<t;
}