58 lines
1.8 KiB
C
58 lines
1.8 KiB
C
/* Contains code to create a linked list of prime numbers. */
|
|
|
|
#include <stdlib.h>
|
|
#include <math.h>
|
|
#include "linkedlist.h"
|
|
#include "listprimes.h"
|
|
|
|
elem* first_n_primes(int n) {
|
|
// Return a pointer to the first element in a linked list of the first n
|
|
// primes
|
|
|
|
elem *first_prime = create(2, NULL), *cur_prime = first_prime;
|
|
int cur_val = 3, list_len = 1;
|
|
|
|
// Iterate until list of primes is desired length
|
|
while (list_len < n) {
|
|
if (is_prime(cur_val, first_prime)) { // cur_val is prime
|
|
cur_prime = create(cur_val, cur_prime); // add to linked list
|
|
list_len ++;
|
|
// printf("(%i) %i\n", list_len, cur_val);
|
|
}
|
|
cur_val += 2;
|
|
}
|
|
return first_prime;
|
|
}
|
|
|
|
elem* primes_lte_n(int n) {
|
|
// Return a pointer to the first element in a linked list of all primes
|
|
// less than or equal to `n`
|
|
elem *first_prime = create(2, NULL), *cur_prime = first_prime;
|
|
int cur_val = 3, list_len = 1;
|
|
|
|
// Iterate until all primes less than n have been considered
|
|
while (cur_val <= n) {
|
|
if (is_prime(cur_val, first_prime)) { // cur_val is prime
|
|
cur_prime = create(cur_val, cur_prime); // add to linked list
|
|
list_len ++;
|
|
// printf("(%i) %i\n", list_len, cur_val);
|
|
}
|
|
cur_val += 2;
|
|
}
|
|
return first_prime;
|
|
}
|
|
|
|
int is_prime(int x, elem* first_prime) {
|
|
// Check if x is prime, given a linked list of prime numbers (assumed
|
|
// valid)
|
|
elem* cur_prime = first_prime;
|
|
double sqrtx = sqrt((double)x);
|
|
// Iterate through each element of the linked list
|
|
while (cur_prime != NULL) {
|
|
if (x % cur_prime->val == 0) return 0;
|
|
else if (cur_prime->val > sqrtx) return 1;
|
|
else cur_prime = cur_prime->next;
|
|
}
|
|
return 1;
|
|
}
|