Algorithm for PRIMES working on ideone but not accepted here!

[ankan1006]

When I run this code in ideone with 1 million number primes it works fine but this is generating SIGKILL upon submitting the code.
This is the code that I used to solve the Primes problem :

#include <stdio.h>
#include <stdlib.h>

int main(){
	int t;
	scanf("%i", &t);
	if(t > 10)
		exit(1);

	unsigned long m[t], n[t];
	for(int i=0; i<t; i++){
		scanf("%li %li", &m[i], &n[i]);
		if(m[i] < 1 || n[i] > 1000000000)
			exit(1);
		if((n[i]-m[i]) > 100000)
			exit(1);
	}


	for(int i=0; i<t; i++){
		int prime[n[i]+1];
		
		if(m[i] < 2) m[i] = 2;

		for(long j=0; j<=n[i]; j++){
			prime[j] = 1;
		}

		for(long p=2; p*p<=n[i]; p++){
			if(prime[p] == 1){
				for(long q=p*p; q<=n[i]; q+=p)
					prime[q] = 0;
			}
		}

		for(long j=m[i]; j<=n[i]; j++){
			if(prime[j] == 1)
				printf("%li\n", j);
		}

		printf("\n");
	}

	return 0;
}

[simes]

I tried it on ideone, and with the test case below, it gives runtime error. So how did you test it with one billion?

1
999999000 1000000000

[ankan1006]

Sorry, for asking this question but I tried to mean 1 million not billion and I am a beginner so I can’t understand what’s causing the problem in this program because this works fine for inputs smaller than 1 million but anything larger than that causes some weird problems.
By the way thanks for your time.

[ankan1006]

Well I think I figured the mistake out but now this time the Judge says time limit exceeded and may be memory limit too. Now what to do next this is the best algorithm that I can understand…
here’s the code

#include <stdio.h>
#include <stdlib.h>

int main(){
	int t;
	scanf("%i", &t);
	if(t > 10)
		exit(1);

	unsigned long m[t], n[t];
	for(int i=0; i<t; i++){
		scanf("%li %li", &m[i], &n[i]);
	}


	for(int i=0; i<t; i++){
		if(m[i] < 1 || n[i] > 1000000000)
			continue;
		if((n[i]-m[i]) > 100000)
			continue;
		
		unsigned short prime[n[i]+1];
		
		if(m[i] < 2) m[i] = 2;

		for(long j=0; j<=n[i]; j++){
			prime[j] = 1;
		}

		for(long p=2; p*p<=n[i]; p++){
			if(prime[p] == 1){
				for(long q=p*p; q<=n[i]; q+=p)
					prime[q] = 0;
			}
		}

		for(long j=m[i]; j<=n[i]; j++){
			if(prime[j] == 1)
				printf("%li\n", j);
		}

		printf("\n");
	}

	return 0;
}

[simes]

The runtime error is because you can’t allocate enough memeory to sieve up to one billion. And if you could allocate the memory, the program would take too long to run. (Even if you didn’t re-calculate prime numbers for each test case.)

You need to come up with a better algorithm. There have been many previous questions asked about this problem. Search this forum and you’ll likely find some ideas.

Good luck!

[ankan1006]

Well I have found a better algorithm i.e. segmented sieve that reduces the memory (shows 4.7M down from 2048M) usage significantly but still somehow the judge says that It gives wrong answers.
why is this giving me wrong answer?

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

void simpleSieve(int start, int limit, int* prime, int* pointer){
	int marks[limit + 1];
	for(int i=0; i<limit; i++)
		marks[i] = 1;

	for(int p=2; p*p<limit; p++){
		if(marks[p]){
			for(int i=p*p; i<limit; i+=p)
				marks[i] = 0;
		}
	}

	for(int i=2; i<limit; i++){
		if(marks[i]){
			prime[*pointer] = i;
			*pointer = *pointer + 1;
			if(i>=start)
				printf("%i\n", i);
		}
	}

}

void segmentedSieve(int m, int n){
	int limit = floor(sqrt(n)) + 1;
	int prime[(int)floor((int)(limit/2))];
	int pointer = 0;
	simpleSieve(m, limit, prime, &pointer);

	int low = (m>limit)?m:limit;
	int high = low + limit;

	while(low < n){
		if(high >= n)
			high = n;

		int mark[limit + 1];
		for(int i=0; i<=limit; i++)
			mark[i] = 1;

		for(int i=0; i<pointer; i++){
			int loLim = floor((int)(low/prime[i])) * prime[i];
			if(loLim < low)
				loLim += prime[i];

			for(int j=loLim; j<=high; j+=prime[i])
				mark[j-low] = 0;
		}

		for(int i=low; i<=high; i++){
			if(mark[i-low])
				printf("%i\n", i);
		}

		low +=limit;
		high += limit;
	}
}

int main(){
	int t;
	scanf("%i", &t);
	int m[t], n[t];

	for(int i=0; i<t; i++)
		scanf("%i %i", &m[i], &n[i]);

	for(int i=0; i<t; i++){
		if(m[i] < 1 || n[i] > 1000000000)
			continue;
		if(n[i]-m[i] >= 100000)
			continue;
		segmentedSieve(m[i], n[i]);
		printf("\n");
	}

	return 0;
}

Should I exit if one of edge case is met like (m-n) is greater than 1k?
And thanks for your precious time…

[simes]

Check your output for this test case carefully.

1
101 200

[ankan1006]

Well Thank You for your time and support…
The bug turn out to be an equals sign that should not belong there…🤦
Finally…

[ankan1006]

Sir It would be really helpful if You can tell me what’s wrong on another problem that Also gives wrong answer but I can’t find which input is causing the issue…
The problem is based on Palindrome:

#include <stdio.h>
#include <stdlib.h>

int isPalin(long number){
	long a = number;
	long b = 0;
	while(a>0){
		b = b * 10 + a % 10;
		a /= 10;
	}
	if(b == number)
		return 1;
	return 0;
}

int main(){
	int t;
	scanf("%i", &t);
	long k[t];

	for(int i=0; i<t; i++){
		char s[10];
		scanf("%s", s);
		k[i] = atoi(s);
	}

	for(int i=0; i<t; i++){
		if(k[i] > 1000000)
			continue;
		long a = k[i] + 1;
		while(!isPalin(a))
			a++;
		printf("%i\n", a);
	}

	return 0;
}

Thank You once more for supporting…

[simes]

You’ve misread the constraints. The number can contain 1 million digits.

[ankan1006]

Now I’ve got the problem and solved it but The Judge says SIGABRT for some reason.
I guess it’s using a lot of memory but when I tested it in ideone it is showing memory usage in KBs.
So i couldn’t get any idea about the bug…
Here’s the code:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

char *strrev(char *str){
	char *p1, *p2;
	if(!str || !*str)
		return str;
	for( p1 = str, p2 = strlen(str)+str-1; p1<p2; ++p1, --p2){
		*p1 ^= *p2;
		*p2 ^= *p1;
		*p1 ^= *p2;
	}
	return str;
}

void append(char *s, char c){
	int len = strlen(s);
	s[len] = c;
	s[len + 1] = '\0';
}

char *removeLeadingZeros(char *s){
	char *tmp;
	for(int i=0; i<strlen(s); i++){
		if(s[i] != '0'){
			tmp = s+i;
			break;
		}
	}
	return tmp;
}

void palin(char *s){
	//printf("s: %s\n", s);
	int midpoint = floor(strlen(s)/2);
	char p[midpoint];
	char q[midpoint];
	int odd = strlen(s) % 2;
	strncpy(p, s, midpoint);
	p[midpoint] = '\0';
	strcpy(q, s+midpoint+odd);
	//printf("p: %s\tq: %s\n", p, q);
	int i=midpoint-1, j=0;
	do{
		int a, b;
		a = p[i];
		b = q[j];
		if(a == b){
			i--;
			j++;
			continue;
		}
		if(a < b){
			if(odd)
				s[midpoint] += 1;
			else
				p[midpoint-1] += 1;
		}
		break;
	}while(1);
	char rev[strlen(p)];
	strcpy(rev, p);
	strrev(rev);
	//printf("p: %s\nrev: %s\n", p, rev);
	if(odd)
		append(p, s[midpoint]);
	//printf("p: %s\tq: %s\n", p, q);
	strcat(p, rev);
	printf("%s\n", p);
}

int main(){
	int t;
	scanf("%i", &t);
	while(t--){
		char s[1000000];
		scanf("%s", s);
		char *p;
		p = removeLeadingZeros(s);
		s[strlen(s) - 1] += 1;
		palin(p);
	}
	return 0;
}

And let me know if I create a separate thread for this problem.

[simes]

char s[1000000];

What’s the answer for 9? for 99? for 999? So what’s the answer for 1 million 9s and how long is it? And don’t forget room for the trailing null.

Personally, I prefer a separate thread for each problem. (and each user. I don’t generally answer people who tack their question onto somebody else’s post.)

[ankan1006]

I have created a separated thread for this problem.
Please check it out and see if you can help with that…
here’s the link