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?
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.
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.
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
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 :/
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).
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 :)
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: line 14 will instantly return true if it has been previously determined that the number in question is prime. It's a cache optimization.
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.
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.
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.
> 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.