Amicable numbers part 0

Working on this but need a reference copy to see while I am away from home. This lists up all combinations of x from y in order to work out amicable numbers.

#include <iostream>
#include <vector>

using namespace std;

/*
functions that gets passed two "ints"  x and y
and then returns a vector of vectors showing all the different
combinations of chosing x items from y.
This would then be called multiple times to generate indexes
used for fatorisation.

Think about actually creating lists or
something that could be created by the call - but
this is OK for the time being
*/

/*
combos passes integers from and total
and returns a vector of vectors of all combos
*/
vector< vector<unsigned int> > combos(unsigned int, unsigned int);

int main()
{
    //create a vector of vectors that contain ints
    vector < vector<unsigned int> > combinations = combos (10,10);

    for (unsigned int i = 0; i != combinations.size(); i++){
        unsigned int com_length = combinations[i].size();
        cout << "length of vector " << com_length << endl;
            for(unsigned int j = 0; j != com_length; j++){
                cout << combinations[i][j];
            }
            cout << endl;
    }
    return 0;
}




vector< vector<unsigned int> > combos(unsigned int from, unsigned int total){
    vector< vector<unsigned int> > vec;
    for (unsigned int i = 1; i != total; i++){
        vector <unsigned int> temp; //create temp new each time so you get rid of old one and start with a blank
        for (unsigned int j = 1; j != i; j++){
            temp.push_back(j);
        }
        vec.push_back(temp);
    }
    return vec;
}

scopes in c++

Some important points about scope here. This is taken from c++ in a nutshell but I wonder if it is exactly true or properly explained as the behavior is not quite what I expected from the description.

#include <iostream>
#include <ostream>

using namespace std;

/*
This is an abuse of the scope rules.  A scope is a region of code that can have
associated declarations and each declaration adds a name to a scope.  The compiler
works out what scope its in and then checks what names exist to use it.

Scopes include objects, functions, classes etc (stuff in curly {} brackets??).

Some scopes are named - e.g. functions, classes - some are unnamed e.g. statement blocks
such as if statements and for loops.

You can use the :: qualifier in front of a name to tell which scope to look at but most names
are unqualified so the computer has to work out what scope and then what name to look at.

With nested scopes NAMES IN INNERSCOPES CAN HIDE NAMES IN OUTER SCOPES!

The below will print out "in contrast ...10" 10 times and then print out both "x in this scope.."
and "in contrast..." 20 times.

For the first ten times the inner scope is not created so x is 10, then once x in the outscope
is more than 10 the inner scope x is created.
*/

int main()
{
    for (int i = 0; i < 30; i++){
        int x = 10;
        if (x < i){
            double x = 3.14;
            cout << "x in this scope is " << x << " and i is " << i << " and double x is " << x * 2 << endl;
        }
        cout << " in contrast x in this scope is " << x << " and i is " << i << endl;
    }
    return 0;
}

Work out the number of divisors

This program works out the first triangular number to have more than five hundred divisors.

It does so by going through all of the triangular numbers, working out their prime factors which are stored in a vector and then passing the vector to another routine that adds up the total number of each different prime which is stored in another vector.

The total number of divisors is then found by adding one to the number of vectors and then multiplying up.

It is worth thinking about how to reduce the number of iterations and a theory to work out a starting point that would make sure that you were covering the number of factors. The program could also work on seeing if there is some limit or distribution of number of divisors, perhaps related to the frequency of primes themselves.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    void factorize(vector<unsigned long long>&, unsigned long long); //
    void factors_out(vector<unsigned long long>&);
    unsigned long int count_factors(vector<unsigned long long>&);

    //target is the number you want to factorize
    unsigned long long target = 0;
    unsigned long int total_factors = 0;
    unsigned int tri = 1;

        while (total_factors < 501){
            target = target + tri;
            tri++;
            vector<unsigned long long> factor_list (1,1);
            factorize(factor_list, target);
            total_factors = count_factors(factor_list);
        }

    cout << "the answer is " << target;
    return 0;
}


//factorize is called recursively and modifies the vector, vec, that is passed by reference
void factorize (vector<unsigned long long>& vec, unsigned long long num){

    unsigned long long test_num = 2; //start with 2 to see if 2 is a factor
    unsigned long long limit_num = num - 1; //change this to square root later in order to speed up
    bool found_factor = false; //assume you have not found a factor

    while (test_num < limit_num){
        if (num % test_num == 0){
            found_factor = true;
            vec.push_back(test_num); //vec was passed by reference
            num = num/test_num;
            test_num = limit_num; //you found a factor, so move to end of while loop to finish it
            }
        test_num++;
    }
    if (found_factor == true){
        factorize(vec, num); //if you found a factor, re run with the number rounded down
    }
    else {
        vec.push_back(num); //you didn't find a factor, so the last number must be prime as well!
        return; //you didn't find another factor so finish
    }
}


void factors_out (vector<unsigned long long>& output_vec){

cout << "size of factor list " << output_vec.size() << endl;

    //size()method on vectors for number of elements
    unsigned int j = 0;
    while (j != output_vec.size()){
        cout << j << " one in the list " << output_vec[j] << endl;
        j++;
    }
    cout << "end of list"  << endl;
}


/*
simplify count factors by not actually recording the different primes but
instead create a vector that counts up the number of each different type of prime
and then calculates the number of divisors at the end
*/

unsigned long int count_factors (vector<unsigned long long>& count_vec){

    vector<unsigned int> primes_count; // a vector to store the count of different primes
    unsigned long long current_prime = count_vec[0];  //the first prime - this will always be 1
    unsigned int count_current_prime = 1; //we have one example of the first prime

    //make a vector that totals up the primes
    for (unsigned int k = 1; k != count_vec.size(); k++){
        if (count_vec[k] == current_prime) {
            count_current_prime++;
        }
        else {
            primes_count.push_back(count_current_prime);
            count_current_prime = 1;
            current_prime = count_vec[k];
        }
    }

    //now work out the number of factors
    unsigned long int total_factors = 1;
    for (unsigned int h = 0; h != primes_count.size(); h++) {
        total_factors *= (primes_count[h] + 1);
     }

    return total_factors;
}

Recursive factorisation passing vector by reference

This program helped solve Project Euler problem 3.

#include <iostream>
#include <vector>
#include <ctime>

using namespace std;

int main()
{
//prototype a function that passes an int and a vector of ints by reference and which returns a result that uses push_back on a vector
void factorize(vector<unsigned long long>&, unsigned long long);

//target is the number you want to factorize
unsigned long long target = 0;
cout << "what number should I factorize?" << endl;
cin >> target;

//factor_list is the vector that is passed by reference
vector<unsigned long long> factor_list (1,1);

unsigned int start = clock();

//call factorize function - note although you are passing by reference this is only mentioned in the prototype and function, not the function call!!
factorize(factor_list, target);

cout << "time taken in milliseconds "  << clock()-start;

cout << "size of factor list " << factor_list.size() << endl;

//size()method on vectors for number of elements
unsigned int j = 0;
while (j != factor_list.size()){
    cout << j << " one in the list " << factor_list[j] <<endl;
    j++;
}
    return 0;
}

//factorize is called recursively and modifies the vector, vec, that is passed by reference
void factorize (vector<unsigned long long>& vec, unsigned long long num){

    unsigned long long test_num = 2; //start with 2 to see if 2 is a factor
    unsigned long long limit_num = num - 1; //change this to square root later in order to speed up
    bool found_factor = false; //assume you have not found a factor

    while (test_num < limit_num){
        if (num % test_num == 0){
            found_factor = true;
            vec.push_back(test_num //vec was passed by reference
            num = num/test_num;
            test_num = limit_num; //you found a factor, so move to end of while loop to finish it
            }
        test_num++;
    }
    if (found_factor == true){
        factorize(vec, num); //if you found a factor, re run with the number rounded down
    }
    else {
        vec.push_back(num); //you didn't find a factor, so the last number must be prime as well!
        return; //you didn't find another factor so finish
    }
}

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;
}

Introducing struct

Struct - structures - are similar to classes. Not sure of the difference. This also is the first time to use functions passing by address rather than by value - note the & syntax and that the function declaration and its definition both use the &. Note that using the const parameter can help reduce the risk of a variable being incorrectly modified when passed by reference.

#include <iostream>

using namespace std;

//Time has to be declared before its use in a function definition
 struct Time {
        int hour, minute;
        double second;
    };

//you don't put the parameter in the initial function declaration
// this function passes by address, not by value
void print_time(Time&);



int main()
{

  Time time = { 11, 59, 3.14159}; //you can assign numbers in order
  print_time(time);
    return 0;
}

the bool type and the const qualifier

Below are a few points about bools and const.

Note that bool is an integer type but const is a qualifier, used when declaring other types - e.g. an int or a short - as a constant value.

Advantages of the const qualifier over the #define directive are that (1) you can define the type of the constant at the time, (2) you can use c++s scoping rules to limit scope if you want (3) you can use the const value to declare the size of an array.

bool is_ready = true; //normal use of bool

int ans = true; //ans assigned 1
int promise = false; //promise assigned 0 

bool start = -100; //start assigned true - any NON ZERO value is converted to true
bool stop = 0; //stop is assigned false - only ZERO is converted to false

const int MONTHS = 12; //MONTHS is symbolic constant for 12

const int toes; //value of toes is UNDEFINED!
toes = 10; //too late - you have messed up and cannot modify it now