primes.c (1691B)
1 /*** 2 * primes.c 3 * 4 * generate an singly-linked list of the first n primes 5 ***/ 6 7 #include <stdio.h> 8 #include <stdlib.h> 9 10 // from http://cs/courses/fall2008/algorithms/code/c_examples/node_list.c 11 typedef struct prime_type *prime; 12 struct prime_type { 13 int value; 14 prime next; 15 }; 16 17 // constructor for single prime node 18 prime new_prime(int value, prime next) { 19 prime self = (prime) malloc(sizeof(struct prime_type)); 20 if (self){ // don't do this if memory wasn't allocated. 21 self->value = value; // set fields 22 self->next = next; 23 } 24 return self; 25 } 26 27 // given a number and a list of all primes lower than that number, 28 // determine if number is prime 29 int is_prime(int n, prime prime_node) { 30 while (prime_node != NULL) { 31 if (n % prime_node->value == 0) { 32 return 0; 33 } 34 prime_node = prime_node->next; 35 } 36 return 1; 37 } 38 39 // given a list of primes, find the next prime to add to the list 40 int next_prime(prime first, int last_prime) { 41 int to_check = last_prime + 1; 42 while (!is_prime(to_check,first)) { 43 to_check++; 44 } 45 //printf(" the prime after %d is %d\n", last_prime, to_check); 46 return to_check; 47 } 48 49 // build list of n primes, return first 50 prime first_n_primes(int n) { 51 prime first = new_prime(2,NULL); 52 prime cur = first; 53 while (n > 1) { 54 n--; 55 prime next = new_prime(next_prime(first, cur->value), NULL); 56 cur->next = next; 57 cur = next; 58 } 59 60 return first; 61 } 62 63 // print list of primes 64 int print_primes(prime first) { 65 prime cur = first; 66 printf(" list of primes: "); 67 while (cur != NULL) { 68 printf("%d ", cur->value); 69 cur = cur->next; 70 } 71 printf("\n"); 72 73 return 0; 74 } 75 76 int primes_test() { 77 prime first = first_n_primes(10); 78 return print_primes(first); 79 }