LinuxQuestions.org - [SOLVED] Optimizing C++ prime tester

Page 1 of 2

Show 50 post(s) from this thread on one page

- Programming (https://www.linuxquestions.org/questions/programming-9/)

- - Optimizing C++ prime tester (https://www.linuxquestions.org/questions/programming-9/optimizing-c-prime-tester-891455/)

SkyerSK

07-13-2011 05:36 AM

Optimizing C++ prime tester

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 (Post 4414177)

...
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 (Post 4414152)

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 (Post 4414188)

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 (Post 4414195)

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 (Post 4414195)

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

All times are GMT -5. The time now is 11:38 PM.

Page 1 of 2

Show 50 post(s) from this thread on one page