Problem Link: SSEC006
Problem:
Two friends who are good in mathematics and one of them challenged the other one to find the Prime Number in a given range say " A " and " B " , here A & B are the range , but it seems easy to solve , so he twisted the question and said print Prime Number Pair whose multiplication comes in between (A * B) and (A/2 * B/2).
Input:
First Line will be Range A
Second Line will be Range B Output:
Print the Prime Number Pair Input Constraints:
1 ≤ Range ≤ 1000
First range must be smaller than the Second range. Example Input:
10
30 Example Output:
11,13
11,17
11,19
11,23
13,17
13,19
13,23 Explanation:
A = 10 & B = 30 (Range)
Prime Number between A & B = {11, 13, 17, 19 23, 29}
A * B = 300
A/2 * B/2 = 75
- 11 * 13 = 143 (75 ≤ 143 ≤ 300 ) ✓
- 11 * 17 = 187 (75 ≤ 187 ≤ 300 ) ✓
- 11 * 19 = 209 (75 ≤ 209 ≤ 300 ) ✓
- 11 * 23 = 253 (75 ≤ 253 ≤ 300 ) ✓
- 13 * 17 = 221 (75 ≤ 221 ≤ 300 ) ✓
- 13 * 19 = 247 (75 ≤ 247 ≤ 300 ) ✓
- 13 * 23 = 299 (75 ≤ 299 ≤ 300 ) ✓
Rest of the number will not come in between the range
Solution:
#include<bits/stdc++.h>
using namespace std;
void simpleSieve(int limit, vector &prime)
{
bool mark[limit + 1];
memset(mark, false, sizeof(mark));
for (int i = 2; i <= limit; ++i)
{
if (mark[i] == false)
{
prime.push_back(i);
for (int j = i; j <= limit; j += i)
{
mark[j] = true;
}
}
}
}
void primesInRange(int low, int high)
{
int i, j;
vector r;
int limit = floor(sqrt(high)) + 1;
vector prime;
simpleSieve(limit, prime);
int n = high - low + 1;
bool mark[n + 1];
memset(mark, false, sizeof(mark));
for (int i = 0; i < prime.size(); i++)
{
int loLim = floor(low / prime[i]) * prime[i];
if (loLim < low)
loLim += prime[i];
if (loLim == prime[i])
loLim += prime[i];
for (int j = loLim; j <= high; j += prime[i])
mark[j - low] = true;
}
for (int i = low; i <= high; i++)
{
if (!mark[i - low])
{
r.push_back(i);
}
}
sort(r.begin(), r.end());
int max = low * high;
int min = (low / 2) * (high / 2);
for (i = 0; i < r.size(); i++)
{
for (j = i + 1; j < r.size(); j++)
{
if ((r[i] * r[j] <= max) && (r[i] * r[j] >= min))
{
cout << r[i] << “,” << r[j] << “\n”;
}
}
}
}
int main()
{
int low, high;
cin >> low >> high;
primesInRange(low, high);
return 0;
}