mathtools/mathtools.h at main · i2aac/mathtools · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <stdio.h> //printf, scanf
#include <stdbool.h> //bool
#include <stdlib.h> //calloc, free
#include <math.h> //sqrt

void swap(unsigned long long *pA, unsigned long long *pB){ //swaps the values at two addresses
    unsigned long long temp = *pA;
    *pA = *pB;
    *pB = temp;
    return;
}

bool is_prime(unsigned long long n){ //returns true if a number is prime
    if(n == 2 || n == 3 || n == 5){
        return true;
    }
    if(n == 0 || n == 1 || (n >> 1) * 2 == n || n % 3 == 0){ //bitshifting is faster than modulo
        return false;
    }
    for(unsigned long long i = 5; i * i <= n; i += 6){
        if(n % i == 0 || n % (i + 2) == 0){
            return false;
        }
    }
    return true;
}

void list_primes(unsigned long long a, unsigned long long b, unsigned long long *num){

    unsigned long long tally = 0;

    if(a > b){ //ensures that a is the smaller of the two numbers
        swap(&a, &b);
    }
    if(b == 0){
        //deal with a range of [0, 0]
        return;
    }

    /*
    this is an implementation of the sieve of eratosthenes
    positions in the array numbers[] will represent n, and the value at the position will indicate primality
    prime numbers will be marked with 0 (false), and composite numbers will be marked with 1 (true)
    */
    bool *numbers = (bool*) calloc(b + 1, sizeof(bool));
    numbers[0] = true;
    numbers[1] = true;

    for(unsigned long long i = 2; i <= b; i++){
        if(!numbers[i]){
            if(i >= a){
                tally++;
                printf("%lli\n", i);
            }
            for(unsigned long long j = i * 2; j <= b; j += i){
                numbers[j] = true;
            }
        }
    }

    *num = tally;

    free(numbers);

    return;
}

void solve_quadratic(double a, double b, double c, double *t1, double *t2, bool *imaginary){
    /*
    This function expresses the roots of a quadratic in the form -b/(2a) +- sqrt(b^2 - 4ac)/(2a).
    This form ensures that imaginary roots can be accounted for in one function.
    */

    double discriminant = b * b - 4 * a * c;
    double denominator = 0.5 / a;
    *imaginary = false;

    if(discriminant < 0){
        discriminant *= (-1);
        *imaginary = true;
    }

    *t1 = b * (-1) * denominator;
    *t2 = sqrt(discriminant) * denominator;

    return;
}

void factorise(unsigned long long n, unsigned long long *num_factors){
    unsigned long long tally = 0, i = 1;
    while(i * i < n){
        if(n % i == 0){
            printf("%lli\t%lli\n", i, n / i);
            tally ++;
        }
        i++;
    }
    tally *= 2;

    if(i * i == n){
        printf("%lli\t(square root)\n", i);
        tally++;
    }

    *num_factors = tally;

    return;
}

void prime_factorise_r(unsigned long long n, unsigned long long *list){
    unsigned long long i;
    for(i = 2; i * i <= n; i++){
        if(n % i == 0){
            prime_factorise_r(i, list);
            prime_factorise_r(n / i, list);
            return;
        }
    }

    list[n]++;

    return;
}

void prime_factorise(unsigned long long n){
    unsigned long long *num_of_each = (unsigned long long *) calloc(n + 1, sizeof(unsigned long long)), tally = 0;

    prime_factorise_r(n, num_of_each);

    for(unsigned long long i = 2; i <= n; i++){
        if(!!num_of_each[i]){
            printf("%lli^%lli\n", i, num_of_each[i]);
            tally += num_of_each[i];
        }
    }

    printf("\n%lli has %lli prime factors.\n", n, tally);

    free(num_of_each);

    return;
}