Hello
I am trying to solve the Prime Number generator problem but I receive the Wrong Answer all the time.
Could anyone check my code? I can not figure out what is wrong.
#include
#include
#include
using namespace std;
int t = 0, m = 0, n = 0, counter = 0;
vector marks;
vector primes;
vector marks_in_range;
int main()
{
cin >> t;
while (counter < t)
{
cin >> m >> n;
//calculate limit
int limit = ((int)sqrt(n)) + 1;
//fill-in table for given limit
for (int i = 0; i <= limit; i++)
{
marks.push_back(true);
}
//find primes for given limit
for (int i = 2; i <= limit; i++)
{
if (marks[i] == true)
{
primes.push_back(i);
for (int j = i; j <= limit; j += i)
{
marks[j] = false;
}
}
}
//calculate range
int range = n - m + 1;
//fill-in table for given range
for (int i = 0; i <= range; i++)
{
marks_in_range.push_back(true);
}
//use primes found for limit to find primes in range
for (int i = 0; i < primes.size(); i++)
{
int loLim = ((int)(m / primes[i])) * primes[i];
if (loLim < m)
{
loLim += primes[i];
}
if (loLim == primes[i])
{
loLim += primes[i];
}
for (int j = loLim; j <= n; j += primes[i])
{
marks_in_range[j - m] = false;
}
}
//display primes in given range
for (int i = m; i <= n; i++)
{
if (i == 1)
{
continue;
}
else if (marks_in_range[i - m] == true)
{
cout << i << endl;
}
}
cout << endl;
counter++;
}
return 0;
}
created
last reply
- 3
replies
- 773
views
- 2
users
- 3
links