Skip to content

Instantly share code, notes, and snippets.

@dangarbri
Created May 8, 2022 13:37
Show Gist options
  • Save dangarbri/16c26413cfc354d87118a8e831f5134a to your computer and use it in GitHub Desktop.
Save dangarbri/16c26413cfc354d87118a8e831f5134a to your computer and use it in GitHub Desktop.
small program to calculate the sum of the first n prime numbers
all:
gcc -g -o sum_prime sum_prime.c number_parser.c -lm
#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;
}
#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
#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