??? Any Suggestions for Speeding This Up ???

I recently made a program that looks for quadratic equations (ax²+bx+c = N) that, when incremented values of x are inputted, generate a lot of prime numbers. The problem is, when going for 10000 or 100000 different values for x, it has to check each result N for primality, which is slow. Plus, it checks for all combinations of a, b, and c, over a range, which REALLY slows it down.

Any suggestions for speeding up this program at all? Even a little bit will speed it up, because this is on the order of millions or billions of math calculations and loops.

Thanks.

Code:

---

#include <iostream>
#include <string>
#include <cstdlib>
#include <stdio.h>
#include <math.h>
#include <ctype.h>

using namespace std;

void main(){
       
       
        short amin;
        short amax;
        short bmin;
        short bmax;
        short cmin;
        short cmax;
        short iterations;
        float pmin;
        float pmax;


        cout << "ax^2 + bx + c" << endl;
        cout << " " << endl;

        //RANGE FOR A
        cout << "Range for a? (integers -32,768 to 32,767)" << endl;
        cout << " " << endl;
        cout << "min? ";
        cin >> amin;
        cout << " " << endl;
        cout << "max? ";
        cin >> amax;
        cout << " " << endl;
        cout << " " << endl;

        //RANGE FOR B
        cout << "Range for b? (integers -32,768 to 32,767)" << endl;
        cout << " " << endl;
        cout << "min? ";
        cin >> bmin;
        cout << " " << endl;
        cout << "max? ";
        cin >> bmax;
        cout << " " << endl;
        cout << " " << endl;
       
        //RANGE FOR C
        cout << "Range for c? (integers -32,768 to 32,767)" << endl;
        cout << " " << endl;
        cout << "min? ";
        cin >> cmin;
        cout << " " << endl;
        cout << "max? ";
        cin >> cmax;
        cout << " " << endl;
        cout << " " << endl;


        //ITERATIONS

        cout << "How many iterations? (no more than 65,535)" << endl;
        cin >> iterations;
        cout << " " << endl;
        cout << " " << endl;

         
        //PERCENTAGE PRIME

        cout << "What percentage should be Prime? (integer 0 to 100)" << endl;
        cout << " " << endl;
        cout << "min? ";
        cin >> pmin;
        cout << " " << endl;
        cout << "max? ";
        cin >> pmax;
        cout << " " << endl;
        cout << " " << endl;

        cout << "Wait..." << endl;
        cout << " " << endl;
        cout << " " << endl;

        float percentmin = pmin/100;
        float percentmax = pmax/100;
       

        //START

        //Values for A
        for (short a = amin; a <= amax; a++)
        {
               
                if(a==0)        //skips the linears
                {
                }
               
               
                else
                {
                        //Values for B
                        for (short b = bmin; b <= bmax; b++)        //CHANGE BACK TO b++
                        {
                       
                                //Values for C
                                for (short c = cmin; c <= cmax; c++)        //CHANGE BACK TO c++
                                {               
                               
                                        //keeps track of how many primes result for this quadratic
                                        unsigned short primes = 0;       

                                        //keeps track of the total iterations for this quadratic
                                        unsigned short total = 0;       
                               
                                        //START of test for increasing values of i
                                        for(short i=0;i<iterations;i++)
                                        {
                       

                                                short flag = 0;

                                                __int64 n = ((a*i*i) + (b*i) + c);
               
                                                if(n>1)
                                                {
                                                        if((n%2)==0)        //checks against 2
                                                        {               

                                                                flag = 1;
                                                        }
                       
                                                        else
                                                        {

                                                                // checks odds from 3 up to sqrt(n)
                                                                for(long m = 3;m<=((long)(sqrt(n)));m+=2)       
                                                                {       
                               
                                                                        if((n%m)==0)
                                                                        {       
                                       
                                                                                flag = 1;
                                                                                break;
                       
                                                                        }

                                                                }

                                                        }
               
               
                                                        if(flag==0)
                                                        {

                                                                primes = primes + 1;

                                                        }

                                                        total++;

                                                }

                                                else
                                                {
                                                        /*cout << " " << endl;
                                                        cout << "---------------------------------------" << endl;
                                                        cout << n << " was tossed out for being <= 1..." << endl;
                                                        cout << "---------------------------------------" << endl;
                                                        cout << " " << endl;*/
                                                }

               
                                        }

                                        double primepercent =  ((double) primes) /(iterations);

                                        if((primepercent >= percentmin) && (primepercent <= percentmax))
                                        {
                                       

                                                cout << " " << endl;
                                                cout << a << "x^2 + " << b << "x + " << c << endl;
                                                cout << primes << " out of " << total << " were prime." << endl;
                                       
       
                                                //cout << primes << endl;
                                       
                                        }

                                }

                        }
               
                }

        }
       
}

---

in the C board a few weeks back was posted some quicker prime number methods

Quicker how? I think my method is as fast as it gets. It checks 2, then all of the odds up to sqrt(N).... The only thing that might be faster would be to have an array of predetermined numbers (all the primes from 2 up to a really large number), and have it check them against N (only going up to sqrt(N))... But, I have no clue how to make anything like that. My professor was horrible :(

If anyone could provide the code for this array setup I've described above, or any other way for the program to go faster (even a little bit), i would appreciate it. :D

First thing I would do would look at the formatting, and consider moving some of the code into another function to make it easier to see what is going on.

A single function with getting on for 200 lines, and what seems like 10 nested levels is not nice to look at.

But for now, I would replace this
&nbsp;&nbsp;&nbsp;&nbsp;for(long m = 3;m<=((long)(sqrt(n)));m+=2)
with this
&nbsp;&nbsp;&nbsp;&nbsp;long limit=(long)sqrt(n);
&nbsp;&nbsp;&nbsp;&nbsp;for(long m = 3;m<=limit;m+=2)

Oh, and main returns an int, not void
int main ( ) {
&nbsp;&nbsp;&nbsp;&nbsp;// your code
&nbsp;&nbsp;&nbsp;&nbsp;return 0;
}

Thanks for your suggestions. I tested the first one, limit = (long)sqrt(N), versus the original, and it cut 10 seconds off (16 instead of 26). woohoo

I don't know why the second suggestion (making main an int instead of a void) would speed it up... oh well :D

>I don't know why the second suggestion (making main an int instead of a void) would speed it up
It wouldn't effect the speed at all, but it would make your code more correct. :)

-Prelude

Well so long as your values don't grow too large, then create a table with a search facility

Code:

---

#include <cmath>
#include <cstdlib>
#include <iostream>
#include <iomanip>
using namespace std;

// See prime number theorem at
// http://www.utm.edu/research/primes/howmany.shtml
// this tells you how big your table may grow
// depending on how many you want to store
const int MAX_NUM = 100;
const int MAX_PRIMES = 50;

int primes[MAX_PRIMES];
int num_primes = 0;

void generate_table ( void ) {
    int i,j;

    num_primes = 0;
    primes[num_primes++] = 2;
    for ( i = 3 ; i < MAX_NUM ; i++ ) {
        int lim = (int)sqrt((double)i);
        bool composite = false;
        for ( j = 2 ; j <= lim && !composite ; j++ ) {
            composite = i % j == 0;
        }
        if ( !composite ) {
            primes[num_primes++] = i;
        }
        if ( num_primes == MAX_PRIMES ) {
            cout << "Table Full" << endl;
            return;
        }
    }
}

void print_table ( void ) {
    int i;
    for ( i = 0 ; i < num_primes ; i++ ) {
        cout << primes[i] << endl;
    }
    cout << "Expected number of primes is "
        << (int)(MAX_NUM/log((double)MAX_NUM))
        << endl;
    cout << "Actual  number of primes is "
        << num_primes
        << endl;
}

// a pair of functions to conduct a binary search of
// the table of primes created previously
int compare ( const void *key, const void *data ) {
    const int *key_ptr = (const int*)key;
    const int *data_ptr = (const int*)data;
    if ( *key_ptr < *data_ptr ) return -1;
    if ( *key_ptr > *data_ptr ) return +1;
    return 0;
}
bool search_table ( int test_val ) {
    return bsearch( &test_val, primes, num_primes, sizeof(primes[0]), compare ) != NULL;
}

int main ( ) {
    generate_table();
    print_table();
    for ( int i = 1 ; i < MAX_NUM ; i++ ) {
        if ( search_table(i) ) {
            cout << i << " is prime" << endl;
        }
    } 
    return 0;
}

---

Experiment a little - store the first 10000 primes in this table, and run your search loop thereafter

Something like

Code:

---

if ( x <= primes[num_primes-1] ) {
    // its in the table, use search_table(x)
} else {
    // x is too big to be in the table, start the search loop
}

---