Sunday, October 27, 2013

First prime number program

Program to calculate list of prime numbers - first 50,000 primes found in around 40 seconds.
#include <iostream>
#include <vector>

using namespace std;

//add_primes passes a complete list of prime numbers along with how many you want to add
//you can pass a vector "normally" - i.e. by value but this means that you copy the vector which is not so efficient
//you may want to pass by reference instead or also use const in order to prevent changes
//note you have to specify what type of vector as well or it just wont work at all!!
vector<unsigned long int> add_primes(vector<unsigned long int>, int);

int main()
{
    //set up some initial primes
    vector<unsigned long int> primes_list;
    primes_list.push_back(2);primes_list.push_back(3);primes_list.push_back(5);

    //ask how many primes you want to add to the list
    int extra_primes = 0;
    cout << "how many prime numbers to you want to add to the list? " << endl;
    cin >> extra_primes;

    primes_list = add_primes(primes_list,extra_primes);

    for (unsigned int i = primes_list.size()-1; i < primes_list.size();i++){
        cout << i+1 << "           " << primes_list[i] << endl;
    }

    return 0;
}

vector<unsigned long int> add_primes(vector<unsigned long int> primes, int add_ons){

    int found_new_primes = 0;
    int target;
    int primes_size;
    int primes_index;
    bool is_a_prime;

    primes_size = primes.size(); //starting number of primes
    target = primes[primes_size-1]; //starting point for search is largest prime in list


    while (found_new_primes < add_ons){

        target++; // increase target and then check if prime
        primes_index = 0; //move to start of list of primes
        is_a_prime = true; //assume target is prime until a divisor is found

        while (primes_index < primes_size){
            if ((target % primes[primes_index]) == 0) {
                is_a_prime = false; //found a divisor
                primes_index = primes_size; //found a divisor so move to the end of the primes list
            }
            primes_index++; //didnt find a divisor so move on to next prime in list
        }

        if (is_a_prime) {
            found_new_primes++;// increment as found a prime
            primes_size++; //increment as found a prime
            primes.push_back(target); //add a prime to the list
        }
    }
    return primes;
}

No comments:

Post a Comment