[SOLVED] Optimizing C++ prime tester

SkyerSK · 07-13-2011, 05:36 AM

Hello,
I'm trying to solve this problem, but always get Time limit exceeded. I've tried my best but still can't get under time limit. Could you please give me some hint about it?

Code:

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
unsigned int num_tests,s_num,e_num,i,act_num,act_div;
cin>>num_tests;
for (i=0;i<num_tests;i++)
	{
	cin>>s_num;cin>>e_num;
	for (act_num=s_num;act_num<=e_num;act_num++)
		{
		for (act_div=sqrt(act_num);act_div>1;act_div--) {if (!(act_num%act_div)) break;}
		if (act_div==1&&act_num!=1) {cout<<act_num<<endl;}
		if (act_num==e_num&&i<num_tests-1) cout<<endl;
		}
	}
}

Thanks much.

dwhitney67 · 07-13-2011, 06:02 AM

Maybe you could consider removing all white-spaces and newlines?

Seriously, I would remove the calls to cout that are in the for-loop. Store the prime numbers in an STL set. When you are done with the loop, then iterate through the set to print out the values. You should not judge the efficiency of your program if you plan to print to standard-out or to a file.

dugan · 07-13-2011, 08:15 AM

Try using the Sieve of Atkins algorithm. It should be much faster than the trial division-based algorithm that you're currently using.

ta0kira · 07-13-2011, 08:24 AM

You should also think about all of the information you're ignoring. For example, all natural numbers except 1 have a prime factorization consisting of numbers less-than or equal-to that number. Therefore, if you know all primes below the number you're testing you only need to divide by those. I'm assuming that's why the problem doesn't have you go from 0 to X; it would be too easy to start at 0. You're on the right track with sqrt, though.

The problem you're solving is "tell me if this number is prime" millions of times. The problem you should be solving is "tell me all of the primes that fall within this range". Even before testing a single number you know that all multiples (>=2) of that number aren't prime. Additionally, if A fails the test when %B, you know that A+xB isn't prime for all integer x.

I think this is more of a computer science problem than a math problem. There are a lot of ways to solve it mathematically, but you need to find one that cuts down both memory and number of redundant operations.
Kevin Barry

SkyerSK · 07-13-2011, 01:26 PM

Thanks for your answers.

dugan: I'll take a look at that algorithm, but at first look it seems to be quite complicated to make.

dwhitney67: Afaik, removing whitespaces etc. won't make any difference. I will try your idea with storing primes, but I'm not sure if won't do more bad than good, as that's one more loop.

ta0kira: I tried to make a little upgrade, here it is:

Code:

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
long int num_of_tests,fst_number,lst_number,i,q,comp=0;
cin>>num_of_tests;
for (i=0;i<num_of_tests;i++) 
	{
	if (i) {cout<<endl;}
	cin>>fst_number;cin>>lst_number; 			
	for (;fst_number<=lst_number;fst_number++)
		{comp=0;
		for (q=2;q<=sqrt(fst_number);q++)	{if (fst_number%q==0) {comp=1;break;} }
		if (!comp&&fst_number!=1) cout<<fst_number<<endl;
		}
	}
}

note: I used comp variable to track if number really is prime, because I don't know how to break two nested loops from inside of one.

The main difference is that it tests numbers ascending, so it should hit the most probable divisors sooner. (2,3 etc.). Also the new line after each "testing session" is now done in first loop - there are less conditions. However, I still can't get through it, and I really don't what to make better. Any further advice?

Thanks.

markush · 07-13-2011, 03:30 PM

You should test only odd numbers:

Code:

#include <cmath>
using namespace std;
int main()
{
    long int num_of_tests,fst_number,lst_number,i,q,comp=0;
    cin>>num_of_tests;
    for (i=0;i<num_of_tests;i++) 
    {
        if (i) {cout<<endl;}
        cin>>fst_number;cin>>lst_number;    
        /* even numbers cannot be prime, let's begin with the next odd number */
        if (fst_number % 2 == 0 && fst_number != 2)
            fst_number++;
        for (;fst_number<=lst_number;fst_number+=2) /* test only odd numbers */
        {comp=0;
            for (q=2;q<=sqrt(fst_number);q++) {if (fst_number%q==0) {comp=1;break;} }
            if (!comp&&fst_number!=1) cout<<fst_number<<endl;
        }
    }
}

If you want to jump out of the loops, you will have to use a function which tests the numbers, here some pseudocode:

Code:

int is_prime(int n)
{
      for (here goes my code
      {
            if (not prime)
                 return 0;
      }
      return 1;
}

Markus

SkyerSK · 07-13-2011, 03:58 PM

Thanks for your reply.
I thought it would be enough to start testing with number 2, it should be the same as with the upgrade you posted.

Quote:

If you want to jump out of the loops, you will have to use a function which tests the numbers, here some pseudocode:

I originally had same idea, but in matter of time (as I always go through limit), I tried to use only one-function code.

markush · 07-13-2011, 04:04 PM

Quote:

Originally Posted by SkyerSK

...
I thought it would be enough to start testing with number 2, it should be the same as with the upgrade you posted...

No, it isn't, I use

Code:

for (;fst_number<=lst_number;fst_number+=2)

which is a step by 2 and makes only one half of the tests.

Markus

ta0kira · 07-13-2011, 04:10 PM

Quote:

Originally Posted by markush

You should test only odd numbers:

I was saying something like this, but more general. For example, if you know 10000 isn't prime, you also know 10000*x for all natural x isn't prime, so you don't need to test them. Similarly, if 10000 is divisible by 2, so is 10000+2x for all integer x, so you don't need to test them.
Kevin Barry

SkyerSK · 07-13-2011, 04:13 PM

Could you please post some symbolic pseudo code? I mean, the concept is really usable, but I doubt it's easy implementation / time requirement.

markush: Sorry, I overlooked that part/concept. I will update the code with that in mind.

markush · 07-13-2011, 04:17 PM

Quote:

Originally Posted by ta0kira

I was saying something like this, but more general.

yes, I've read that

Quote:

For example, if you know 10000 isn't prime, you also know 10000*x for all natural x isn't prime, so you don't need to test them. Similarly, if 10000 is divisible by 2, so is 10000+2x for all integer x, so you don't need to test them.
Kevin Barry

you are right, this is the principle behind the "sieve of Eratosthenes" (or atkins respectivley) but I doubt that this algorithm can be implemented in such a short program as the OP provided.

The fastest program for primes I ever wrote was with an array to store the (already found) prime-numbers and check new numbers only against them. If one uses pointers to run through this array one can learn much about C-programming.

Markus

SkyerSK · 07-13-2011, 04:34 PM

Quote:

Originally Posted by markush

yes, I've read that

The fastest program for primes I ever wrote was with an array to store the (already found) prime-numbers and check new numbers only against them. If one uses pointers to run through this array one can learn much about C-programming.

Markus

I was thinking of same approach

at first. But respecting good manners, I think I should stick with the "standard" way. I haven't tested your advice yet, as it needs some tunning with 2 (eg. testing numbers 1-10, and 1+2=3, which means 2 gets skipped even if it's prime). I will go to sleep now, will check tomorrow.

ta0kira · 07-13-2011, 08:59 PM

Quote:

Originally Posted by markush

The fastest program for primes I ever wrote was with an array to store the (already found) prime-numbers and check new numbers only against them. If one uses pointers to run through this array one can learn much about C-programming.

I've done that, as well, and it's very fast, but you get no points for finding primes below the beginning of the interval, so if might be a waste of time.

Here is how I'd start:

Create an array of flags with either 1 byte or 1 bit per number in the range and set all to 1 indicating that each one is still in the running.
Pick some arbitrary N<begin and set all multiples of [2,N] within [begin,end] to 0 indicating they failed. You might later figure out an ideal N given a range to balance out time it takes for the rest of the algorithm (if you set N=begin, that would be similar to markush's post I quoted). When you do this, also have an array of flags for [2,N] and mark off multiples in that array as you go. This will let you skip e.g. marking off multiples of 6 when you've already marked off multiples of 2.
Set I=0.
Increment I until a non-zero flag is reached.
Test the value corresponding to I (i.e. I+begin) by % by all numbers between N and sqrt(I+begin).
If I+begin fails, mark all multiples of the number that it was % by to fail. Incidentally, this will include all multiples of I+begin.
If I+begin<end repeat from 4.
Iterate the array and print I+begin for all non-zero elements.

Kevin Barry

PS Actually, if you made N=sqrt(end) you'd be done without 4-7.

SkyerSK · 07-14-2011, 07:37 AM

Alright, I made following update to code, it uses different way to get results, just as you guys suggested. It's not exactly what You said, Ta0kira, I'm working on it currently. Yet, I'd like to know why do I get SIGABRT signal for that code:

Code:

#include <iostream>
using namespace std;
int main()
{
long int i,q,end_num,fst_num,s,num_of_tests,testing;
cin>>num_of_tests;
for (testing=0;testing<num_of_tests;testing++)
{
if (testing!=0) cout<<endl;
/* the core */
cin>>fst_num;cin>>end_num;
bool * numbers=new bool[end_num+1];
for (i=2;i<(1+end_num/2);i++)
{
if (numbers[i]==1) continue;

for (q=1;i*q<=end_num;q++) {if (q!=1) {numbers[i*q]=1;}}
}
for (s=2;s<end_num+1;s++) {if (!numbers[s]) cout<<s<<endl;}
delete [] numbers;
}
}

markush · 07-14-2011, 07:48 AM

I've tested your code, here it works.

Markus