Prime Generator (/PRIME1) gives wrong answer

[raghanitsu]

I am having a lot of troubles trying to pass this problem. I made this algorithm written in C:

#include <stdio.h>

int main()
{
	int t;

	scanf("%d", &t);

	while(t--)
	{
		int m, n;
		char primes[100000];
		
		scanf("%d %d", &m, &n);

		if (n < 2)
			return 0;

		if (m <= 2)
			printf("%d\n", 2);

		if (m % 2 == 0)
			m++;
		if (m == 1)
			m = 3;

		for (int i = m; i <= n; i+=2)
		{
			if (primes[i - m] != 'f')
			{
				char prime = 't';
				for(int j = 3; j * j <= i; j+=2)
					if (i % j == 0)
						prime = 'f';
				if(prime == 't')
					printf("%d\n", i);
				else
					for(int j = 1; i * j <= n; j++)
						primes[i * j - m] = 'f';
			}
		}
		printf("\n");

	}

	return 0;
}

For what I can see (and tested) it works perfectly and it follows the output format that was specified, but I get wrong answer when I submit. Can anyone point me in any direction that could help me realize what I’m doing wrong here?

Thanks!

[kartik44]

go through my code for prime generator…
#include
#include<math.h>
#define ll long long
using namespace std;
void prime(ll,ll);
int main()
{
int t;
cin>>t; ll n1,n2;
while(t–)
{
cin>>n1>>n2;
prime(n1,n2);
}
}
void prime(ll n1,ll n2)
{
ll i;
for(i=n1; i<=n2; i++)
{
ll flag=0;
for(ll j=2; j<=sqrt(i); j++)
{
if(i%j==0)
{
flag=1;break;
}
}
if(flag==0&& i!=1)
cout<<i<<endl;
}
cout<<endl;
}

[raghanitsu]

I try to use your code and it worked, thanks! But I don’t understand why mine doesn’t. I tested some outputs and both are exactly the same…

[kartik44]

ur code checks every number and it is not efficient for large inputs
i have used sqrt function to reduce number of operations…

[simes]

@raghanitsu Try this test case with your original code.

2
1 1
1 10

[raghanitsu]

My code also uses sqrt only that instead of using the sqrt() function from math.h it just does j * j <= i. It’s the same than j <= sqrt(i) but I’m not adding the math library for just one line that needs sqrt. Also my code doesn’t check even numbers, just odds (starts on 3 and incremets by 2). It’s even faster than the one that worked.

[raghanitsu]

Thanks for pointing that out, I corrected my error by changing

if (n < 2) return 0;

with

if (n >= 2)

and then putting the entire code (without the printf("\n"); ) into the if.

I still get wrong answer with that though

[simes]

Try this

3
100 230
200 300
220 230

ymmv, but this is what it gave me

101
103
107
109
113
127
131
137
139
149
151
157
163
167
173
179
181
191
193
197
199
211
223
227
229

227
239
251
257
263
281
293

Check for 223, and where’s the third set?

[raghanitsu]

Thanks!! I know what is wrong. The primes array is the problem. It saves which numbers are primes but it is valid only on the first run or as long as the first number (m) it is always the same, the moment it changes, the indexes will represent another numbers and the array will mark them as prime or not prime randomly (actually not randomly, but according to previous inputs of m). I have to figure out a way to correct this or not use it (I think that I should have to implement a dictionary or something of the kind if I want it to work the way I intend it to)

[simes]

I was just thinking it needed initialising between runs.