Commits

sirchristian committed 109cb5e

Added algorithms to store more efficent solutions

  • Participants
  • Parent commits 3c3f48d

Comments (0)

Files changed (3)

File algorithms.c

+#include "algorithms.h"
+
+#ifndef TRUE
+#define TRUE 1
+#endif
+#ifndef FALSE 
+#define FALSE 0
+#endif
+int IsPrime(long n)
+{
+    long r,f;
+    // Translated from the pseduo-code for the sieve of Eratosthenes found
+    // in the solution for problem 7.
+    
+    // 1 or under is never prime
+    if (n <= 1)
+        return FALSE;
+
+    // 2 and 3 are always prime
+    if (n == 2 || n == 3)
+        return TRUE;
+
+    // we got 2 taken care of..all other primes are odd
+    if (n % 2 == 0)
+        return FALSE;
+
+    // We took care of all the negative cases below 9 already
+    if (n < 9)
+        return TRUE;
+
+    // Takes care of common divisor (??) 
+    if (n % 3 == 0)
+        return FALSE;
+
+    // Get an r such that r*r <= n
+    r = floor(sqrt(n)); 
+    f = 5;
+    while (f <= r)
+    {
+        // If we find a factor, not a prime
+        if (n % f == 0)
+            return FALSE;
+        if (n % (f+2) == 0)
+            return FALSE;
+        f += 6;
+    }
+
+    // failed all negative tests...must be prime
+    return TRUE;
+}

File algorithms.h

+#include <math.h>
+#ifndef IS_PRIME_ALGORITHMS
+#define IS_PRIME_ALGORITHMS
+int IsPrime(long n);
+#endif

File problem0007/7_with_algorithm.c

+#include<stdio.h>
+#include "algorithms.h"
+#define NUMPRIMES 10001
+int main()
+{
+	long primes[NUMPRIMES];
+    int numPrimes;
+    int x;
+    numPrimes = ComputePrimes(primes, NUMPRIMES);
+ 
+    printf("Found %d primes. \n\n", numPrimes);
+    for (x=0;x<numPrimes;x++)
+    {
+        char whitespace = (x+1) % 10 == 0 ? '\n' : '\t';           
+        printf("%3d%c", primes[x],whitespace);
+    }
+    printf("\n");
+    return 0;
+}
+ 
+// Computes primes and returns how many primes it calculated
+int ComputePrimes(long primes[], int length)
+{
+    int numPrimes = 1;
+    long x;
+    long* arr = primes;
+ 
+    // First prime
+    *arr = 2;
+    arr++;
+    for (x=3;numPrimes<length;x+=2)
+    {
+        if (IsPrime(x))
+        {
+            *arr = x;
+            arr++;
+            numPrimes++;
+        }
+    }
+    return numPrimes;
+}