Created
May 8, 2022 13:37
-
-
Save dangarbri/16c26413cfc354d87118a8e831f5134a to your computer and use it in GitHub Desktop.
small program to calculate the sum of the first n prime numbers
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
all: | |
gcc -g -o sum_prime sum_prime.c number_parser.c -lm |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdlib.h> | |
#include <errno.h> | |
/** | |
* Converts the input STR to a nunber or exits the program. | |
* thus making any user always have a valid return value or | |
* it won't be executed. | |
*/ | |
unsigned long long safe_parse_decimal(char* str) | |
{ | |
errno = 0; | |
char* tailptr; | |
unsigned long long result = strtoull(str, &tailptr, 10); | |
if (errno) | |
{ | |
perror("Failed to parse integer"); | |
exit(errno); | |
} | |
if (*tailptr != '\0') | |
{ | |
puts("Failed to parse integer"); | |
exit(1); | |
} | |
return result; | |
} |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#ifndef _NUMBER_PARSER_H_ | |
#define _NUMBER_PARSER_H_ | |
/** | |
* Parses positive integers safely. If the string is not an integer | |
* then this function will exit the program, preventing any following | |
* code from executing with an invalid number. | |
*/ | |
unsigned long long safe_parse_decimal(char* str); | |
#endif |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdlib.h> | |
#include <math.h> | |
#include "number_parser.h" | |
typedef unsigned long long number; | |
typedef int bool; | |
#define true 1; | |
#define false 0; | |
/** | |
* Use trial division to determine if a number is prime. | |
* divides n by 2 up to sqrt(n) to determine if it is prime. | |
*/ | |
bool is_prime(number n) | |
{ | |
long double root = sqrtl(n); | |
for (number divisor = 2; divisor <= root; divisor++) | |
{ | |
// if the division works | |
if ((n % divisor) == 0) | |
{ | |
return false; | |
} | |
} | |
return true; | |
} | |
number get_multiplier(number n) | |
{ | |
// When q is 1, need to use the formula 6*1 - 1 | |
// when q is 2, need to use the formula 6*1 + 1 | |
// When q is 3, need to use the formula 6*2 - 1 | |
// When q is 4, need to use the formula 6*2 + 1 | |
// For this to work we need to make a mapping | |
// (1,2) -> 1 | |
// (3,4) -> 2 | |
// (5,6) -> 3 | |
// (7,8) -> 4 | |
// To get this result, if n is odd, add 1 and then divide by 2. | |
// If n is even, then simply divide by 2 | |
// If odd | |
if (n & 1) | |
{ | |
return (n + 1) / 2; | |
} | |
else | |
{ | |
return n / 2; | |
} | |
} | |
number calculate_prime(number n) | |
{ | |
// https://primes.utm.edu/notes/faq/six.html | |
// Formula begins to work at 5, (i.e. 6 * 1 - 1 == 5) | |
number multiplier = get_multiplier(n); | |
// If odd | |
if (n & 1) | |
{ | |
return (6 * multiplier) - 1; | |
} | |
else | |
{ | |
return (6 * multiplier) + 1; | |
} | |
} | |
/** | |
* Tries to return the nth prime number (zero-indexed) | |
* It is not perfect because using the formula 6n +/- 1 does | |
* not always return a prime number, so results should be tested | |
* i.e. 1 -> 2 | |
* 2 -> 3 | |
* 3 -> 5 | |
* 4 -> 7, etc | |
*/ | |
number get_prime(number n) | |
{ | |
if (n == 1) | |
{ | |
return 2; | |
} | |
if (n == 2) | |
{ | |
return 3; | |
} | |
// When using calculate prime, calculate_prime(1) = 5 and | |
// calculate_prime(2) = 7, so when n>3, we must pass n-2 to get | |
// the correct result. This is because the formula used only works for | |
// primes n > 3. | |
number tentative_result; | |
do { | |
tentative_result = calculate_prime(n - 2); | |
n += 1; | |
} while (!is_prime(tentative_result)); | |
return tentative_result; | |
} | |
number sum_primes(number n) | |
{ | |
number primer = 1; | |
number last_prime = 0; | |
number sum = 0; | |
for (number count = 0; count < n; count++) | |
{ | |
// Get the next available prime number | |
number prime = get_prime(primer++); | |
while (prime == last_prime) | |
{ | |
prime = get_prime(primer++); | |
} | |
last_prime = prime; | |
// add it to the sum | |
sum += prime; | |
} | |
return sum; | |
} | |
int main(int argc, char** argv) | |
{ | |
if (argc > 1) | |
{ | |
number in_num = safe_parse_decimal(argv[1]); | |
number result = sum_primes(in_num); | |
printf("%u: %u\n", in_num, result); | |
} | |
else | |
{ | |
puts("Not enough args."); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment