SPOJ

[ETAkoG1T]

I was taking a walk around the internets and found this website called spos were you can submit solutions to problems. It looked great, but I have a problem with my code taking too long, but on my computer it didn't take any time at all. Is this a problem with the code/optimization? Also does anyone know of any similar websites for practicing?

code:

#include <iostream>

void ShowPrimes(int min, int max);

bool isPrime(int n)
{
	for(int i = 2; i < n; i++)
	{
		if(n % i == 0)
			return false;
	}
	return true;
}
int main()
{
	using std::cin;
	int num;
	cin >> num;
	int min, max;
	
	while(num)
	{
		cin >> min;
		cin >> max;
		ShowPrimes(min, max);
		num--;
	}

	return 0;
}

void ShowPrimes(int min, int max)
{
	for(int i = min; i <= max; i++)
	{
		if(isPrime(i))
			std::cout << i << std::endl;
	}
}

[coder777]

Is this a problem with the code/optimization?

Yes, the problem is of course isPrime()

you can improve the speed when you use an array for the already found primes. for a new prime check you just have to use the already found primes.

Also does anyone know of any similar websites for practicing?

sorry, can't remember any the moment

[ETAkoG1T]

used this code but time limit is still exceeded, also I think the program checkes for higher primes to make sure you are not cheating:

#include <iostream>

const int MAX = 20;

int arrStorePrimes[MAX] = { 0 };

void ShowPrimes(int min, int max);

bool isPrime(int n)
{
	if(n == 1)
		return false;

	if(n < MAX && arrStorePrimes[n] != 0)
	{
		return true;
	}
	for(int i = 3; i < n; i += 2)
	{
		if(n % i == 0)
			return false;
	}

	if(n < MAX)
		arrStorePrimes[n] = 1;
	
	return true;
}
int main()
{
	using std::cin;
	int num;
	cin >> num;
	int min, max;
	
	while(num)
	{
		cin >> min;
		cin >> max;
		ShowPrimes(min, max);
		num--;
	}
	std::cin.get();
	std::cin.get();
	return 0;
}

void ShowPrimes(int min, int max)
{
	if( min % 2 == 0 )
		++min;
	for(int i = min; i <= max; i += 2)
	{
		if(isPrime(i))
			std::cout << i << std::endl;
	}
}

Just realized that I used double the amount of operations I need, I don't need to check if it is divisible by 2 4 6 8 ... only need to check 2

Edit: updated code above, still takes too long though :/

[coder777]

Just realized that I used double the amount of operations I need, I don't need to check if it is divisible by 2 4 6 8 ... only need to check 2

More so: you only need to check whether it's divisible by a prime (I thought i stated that?) you don't need to check 9 only 3

there shouldn't be a problem to make the array much larger. 100000 and more shouldn't be a problem. Otherwise it wouldn't have much effect for large numbers.

use bool arrStorePrimes[MAX]; // saves memory
keep the highest stored value. Only when a number exceeds this you need to calculate whether it is a prime number. This will again reduce the number of cycles.

[ETAkoG1T]

can't get it workign :/ This is my current code now it also gives me a couple of errors on the website, but it works perfectly when I run it from visual studio.

#include <iostream>

const int MAX = 20;

bool arrStorePrimes[MAX] = { false };

void ShowPrimes(int min, int max);

bool isPrime(int n)
{
	if(n == 1)
		return false;

	if(n < MAX && arrStorePrimes[n] != false)
	{
		return true;
	}
	for(int i = 3; i < n; i += 2)
	{
		if(n % i == 0)
			return false;
	}

	if(n < MAX)
		arrStorePrimes[n] = 1;
	
	return true;
}
int main()
{
	using std::cin;
	int num;
	cin >> num;
	int min, max;
	
	while(num)
	{
		cin >> min;
		cin >> max;
		ShowPrimes(min, max);
		num--;
	}
	std::cin.get();
	std::cin.get();
	return 0;
}

void ShowPrimes(int min, int max)
{
	if( min % 2 == 0 )
		++min;
	for(int i = min; i <= max; i += 2)
	{
		if(isPrime(i))
			std::cout << i << std::endl;
	}
}

[coder777]

what are these couple of errors?

is there a memory limit? Otherwise multiply the value for MAX with 10000 or more. up to the maximum possible. don't be unnecessaryly cheap.

remove isPrime() and put it all in ShowPrimes(). I guess it's not a beauty contest. It's all about speed.

The array arrStorePrimes is not just about prime numbers, but all available numbers. You just set the prime numbers to true. And all available numbers are somewhat more than just 20, hence increase the number of MAX. The more the better, otherwise you will have a speed effect close to not existing.

but it works perfectly when I run it from visual studio.

you certainly test it only with small numbers. They test it with huge.

Wonder what this min/max means.

Are you able to spend another array to really store the already calculated prime numbers? If so do it and speed up the loop on line 18

[ETAkoG1T]

I don't know if they test it with huge numbers but the computers they test with are really slow... To make it hard. I think there is a memory limit, when I raise the MAX I get some problems. The challenge doesn't say anything about testing huge numbers though.

EDIT: Actually I don't get any errors, but the time limit is still exceeded :/

[Computergeek01]

In case they are using big numbers it's helpful to note that a number is never divisible by more than half of its value. So checking every number 3 through 'n' is using twice as many operations as is needed, you should only be checking 3 through (n / 2).

[ETAkoG1T]

Ok, computergeek, nice tips. It still exceeds the time limit of 6 sec. (not sure if that is including compilation)
http://www.spoj.com/problems/PRIME1/

I really would think making a program like this would be good to do in c++ because it is so low level and fast. I have a feeling I am just doing something different than how the website wants me to do it. Help very much appreciated :)

[MiiNiPaa]

Actually you need only to test numbers from 3 to sqrt(n): If there is divisor larger that square root of number, the result (and paired divisor) will be less than sqrt.

[Computergeek01]

@ Mii Ni Paa: Even better.

@OP: This will help with Mii Ni Paa's suggestion: http://www.cplusplus.com/reference/cmath/sqrt/

Also, it maybe because it's 9:30 AM where I am but what is Line 14 trying to do?

[LB]

@Computergeek01: line 14 will instantly return true if it has been previously determined that the number in question is prime. It's a cache optimization.

[Computergeek01]

Thank you LB, that makes sense. I would have expected OP to use a map<unsigned, bool> container but I see that he is using the index to represent the number and is saving the boolean value to the place in the array that it references. The container would also let him use the "find()" member function.

[3qX21hU5]

Also does anyone know of any similar websites for practicing?

http://ww2.codechef.com/

http://www.topcoder.com/

Haven't tried this one personally but looks alright.
https://www.hackerrank.com/


There is a bunch of websites that cater towards programming problems.

[LB]

Computergeek01 wrote:

Thank you LB, that makes sense. I would have expected OP to use a map<unsigned, bool> container but I see that he is using the index to represent the number and is saving the boolean value to the place in the array that it references. The container would also let him use the "find()" member function.

Using a map would be less efficient - with the c-style array he can determine exactly how much memory he uses and it is a simple pointer addition to access the nth number's prime status.

[3qX21hU5]

Just wanted to say I checked out https://www.hackerrank.com/ after posting the suggestion on here awhile ago and they seem to have some really neat problems. A lot of them deal with artificial intelligence for game buffs though they do have normal algorithm questions also. Nice setup for a competition site also.

[ne555]

> I don't know if they test it with huge numbers
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.


You may want to read the problem statement.


> Also does anyone know of any similar websites for practicing?
http://uva.onlinejudge.org/
http://www.programming-challenges.com/

[ETAkoG1T]

This is my newest working code, but it still exceeds the time limit... Do I have to increase everything to long to get it working?

#include <iostream>
#include <cmath>

const int MAX = 20;

bool arrStorePrimes[MAX] = { 0 };

void ShowPrimes(int min, int max);

bool isPrime(int n)
{
	if(n == 1)
		return false;

	if(n < MAX && arrStorePrimes[n] != 0)
	{
		return true;
	}

        int sq = sqrt(n);

	for(int i = 3; i <= sq; i += 2)
	{
		if(n % i == 0)
			return false;
	}

	if(n < MAX)
		arrStorePrimes[n] = 1;
	
	return true;
}
int main()
{
	using std::cin;
	int num;
	cin >> num;
	int min, max;
	
	while(num)
	{
		cin >> min;
		cin >> max;
		ShowPrimes(min, max);
		num--;
	}
	return 0;
}

void ShowPrimes(int min, int max)
{
	if( min % 2 == 0 )
		++min;
	for(int i = min; i <= max; i += 2)
	{
		if(isPrime(i))
			std::cout << i << std::endl;
	}
}

[coder777]

I have a feeling I am just doing something different than how the website wants me to do it.

Yes, read the requirements carefully: you need to gather all the input (upto 10) and then produce the output.

And yes I'm pretty sure that they test the extreme values. if not what would be the point to mention them in their requirements?

So checked it a little bit:

It's possible to find for 100000 the prime values within 6 sec
But it's impossible for 1000000000 (1 Billion)
[this way]

Hint: there's a solution, but it's a bit bottom up. Near to 'Sieve of Eratosthenes', but not quite

[ne555]

> you need to gather all the input (upto 10) and then produce the output.
Nope.