QUESTION:-
You want to generate some prime numbers for your cryptosystem.
Input
The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.
Output
For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.
Input:
2
1 10
3 5
Output:
2
3
5
7
3
5
Warning: large Input/Output data, be careful with certain languages (though most should be OK if the algorithm is well designed)
Ans:-
You must be thinking I am an idiot that I have tagged this question in cakewalk instead of basics, Believe me, this question is going to give TLE(Time Limit Error) if you are not aware of how to handle large I/O.
I have used a mathematical concept known as "all primes are of the form 6k ± 1, with the exception of 2 and 3". Have a look at the below code:
C++ CODE:-
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
bool is_prime(ll n)
{
if (n <= 1)
{
return false;
}
if (n <= 3)
{
return true;
}
if (n%2 == 0 || n%3 == 0)
{
return false;
}
for (ll i=5; i*i<=n; i=i+6)
{
if (n%i == 0 || n%(i+2) == 0)
return false;
}
return true;
}
int main()
{
ll t;
cin >> t;
while(t--)
{
int m,n;
cin >> m >> n;
for(int i=m;i<=n;i++)
{
if(is_prime(i)==true)
{
cout << i << endl;
}
}
}
return 0;
}
Hope that helps, keep coding :)
Comments
Post a Comment