prim_sieve.c
· 2.9 KiB · C
原始文件
#include <stdint.h>
#include <stddef.h>
#include <stdlib.h>
#include <stdio.h>
#include <signal.h>
#include <math.h>
#include <string.h>
#define ARRAY_DEFAULT_CAPACITY 8
typedef struct {
uint64_t* arr;
size_t length;
size_t capacity;
} uint64_array_t;
uint64_array_t* uint64_array_create() {
uint64_array_t* arr = malloc(sizeof(uint64_array_t));
if (arr == NULL) {
return NULL;
}
arr->capacity = ARRAY_DEFAULT_CAPACITY;
arr->length = 0;
arr->arr = malloc(ARRAY_DEFAULT_CAPACITY * sizeof(uint64_t));
if (arr->arr == NULL) {
free(arr);
return NULL;
}
return arr;
}
void uint64_array_free(uint64_array_t* arr) {
free(arr->arr);
free(arr);
}
uint8_t uint64_array_capacity_increase(uint64_array_t* arr) {
arr->capacity *= 2;
arr->arr = realloc(arr->arr, arr->capacity * sizeof(uint64_t));
if (arr->arr == NULL) {
return 1;
}
return 0;
}
uint8_t uint64_array_append(uint64_array_t* arr, uint64_t value) {
if (arr->length == arr->capacity) {
if (uint64_array_capacity_increase(arr)) {
return 1;
}
}
arr->arr[arr->length] = value;
arr->length += 1;
return 0;
}
typedef struct {
uint64_t u;
uint64_t n;
} args_t;
void parse_args(args_t* args, int argc, char* argv[]) {
args->u = 0;
args->n = 0;
for (size_t i=1; i < argc; i++) {
if (strcmp(argv[i], "-n") == 0 && i + 1 < argc) {
args->n = strtol(argv[++i], NULL, 10);
} else if (strcmp(argv[i], "-u") == 0 && i + 1 < argc) {
args->u = strtol(argv[++i], NULL, 10);
} else if (strcmp(argv[i], "--help") == 0) {
fprintf(stderr, "Usage: sieve\nParameters:\n\t-n NUMBER: Print NUMBER prime numbers\n\t-u NUMBER: Print prime numbers until NUMBER is reached\n\t--help: Show this help\n");
exit(0);
}
}
}
void handle_sigint(int sig) {
fflush(stdout);
exit(0);
}
int main(int argc, char* argv[]) {
args_t args;
parse_args(&args, argc, argv);
signal(SIGINT, handle_sigint);
uint64_array_t* arr = uint64_array_create();
if (arr == NULL) {
perror("Error while allocating space for array");
return 1;
}
uint64_t i = 2;
while (1) {
int limit = (int) sqrt((double) i) + 1;
for (size_t k=0; k < arr->length; k++) {
int p = arr->arr[k];
if (p > limit) break;
if (i % p == 0) {
goto incr;
}
}
printf("%llu\n", i);
if (uint64_array_append(arr, i)) {
goto error;
}
if (args.n > 0 && arr->length == args.n) {
break;
}
incr: i += 1;
if (args.u > 0 && i > args.u) {
break;
}
}
end:
uint64_array_free(arr);
fflush(stdout);
return 0;
error:
uint64_array_free(arr);
perror("Error");
return 1;
}
| 1 | #include <stdint.h> |
| 2 | #include <stddef.h> |
| 3 | #include <stdlib.h> |
| 4 | #include <stdio.h> |
| 5 | #include <signal.h> |
| 6 | #include <math.h> |
| 7 | #include <string.h> |
| 8 | |
| 9 | #define ARRAY_DEFAULT_CAPACITY 8 |
| 10 | |
| 11 | typedef struct { |
| 12 | uint64_t* arr; |
| 13 | size_t length; |
| 14 | size_t capacity; |
| 15 | } uint64_array_t; |
| 16 | |
| 17 | uint64_array_t* uint64_array_create() { |
| 18 | uint64_array_t* arr = malloc(sizeof(uint64_array_t)); |
| 19 | if (arr == NULL) { |
| 20 | return NULL; |
| 21 | } |
| 22 | arr->capacity = ARRAY_DEFAULT_CAPACITY; |
| 23 | arr->length = 0; |
| 24 | arr->arr = malloc(ARRAY_DEFAULT_CAPACITY * sizeof(uint64_t)); |
| 25 | if (arr->arr == NULL) { |
| 26 | free(arr); |
| 27 | return NULL; |
| 28 | } |
| 29 | return arr; |
| 30 | } |
| 31 | |
| 32 | void uint64_array_free(uint64_array_t* arr) { |
| 33 | free(arr->arr); |
| 34 | free(arr); |
| 35 | } |
| 36 | |
| 37 | uint8_t uint64_array_capacity_increase(uint64_array_t* arr) { |
| 38 | arr->capacity *= 2; |
| 39 | arr->arr = realloc(arr->arr, arr->capacity * sizeof(uint64_t)); |
| 40 | if (arr->arr == NULL) { |
| 41 | return 1; |
| 42 | } |
| 43 | return 0; |
| 44 | } |
| 45 | |
| 46 | uint8_t uint64_array_append(uint64_array_t* arr, uint64_t value) { |
| 47 | if (arr->length == arr->capacity) { |
| 48 | if (uint64_array_capacity_increase(arr)) { |
| 49 | return 1; |
| 50 | } |
| 51 | } |
| 52 | |
| 53 | arr->arr[arr->length] = value; |
| 54 | arr->length += 1; |
| 55 | |
| 56 | return 0; |
| 57 | } |
| 58 | |
| 59 | typedef struct { |
| 60 | uint64_t u; |
| 61 | uint64_t n; |
| 62 | } args_t; |
| 63 | |
| 64 | void parse_args(args_t* args, int argc, char* argv[]) { |
| 65 | args->u = 0; |
| 66 | args->n = 0; |
| 67 | |
| 68 | for (size_t i=1; i < argc; i++) { |
| 69 | if (strcmp(argv[i], "-n") == 0 && i + 1 < argc) { |
| 70 | args->n = strtol(argv[++i], NULL, 10); |
| 71 | } else if (strcmp(argv[i], "-u") == 0 && i + 1 < argc) { |
| 72 | args->u = strtol(argv[++i], NULL, 10); |
| 73 | } else if (strcmp(argv[i], "--help") == 0) { |
| 74 | fprintf(stderr, "Usage: sieve\nParameters:\n\t-n NUMBER: Print NUMBER prime numbers\n\t-u NUMBER: Print prime numbers until NUMBER is reached\n\t--help: Show this help\n"); |
| 75 | exit(0); |
| 76 | } |
| 77 | } |
| 78 | } |
| 79 | |
| 80 | void handle_sigint(int sig) { |
| 81 | fflush(stdout); |
| 82 | exit(0); |
| 83 | } |
| 84 | |
| 85 | int main(int argc, char* argv[]) { |
| 86 | args_t args; |
| 87 | parse_args(&args, argc, argv); |
| 88 | |
| 89 | signal(SIGINT, handle_sigint); |
| 90 | |
| 91 | uint64_array_t* arr = uint64_array_create(); |
| 92 | if (arr == NULL) { |
| 93 | perror("Error while allocating space for array"); |
| 94 | return 1; |
| 95 | } |
| 96 | uint64_t i = 2; |
| 97 | while (1) { |
| 98 | int limit = (int) sqrt((double) i) + 1; |
| 99 | for (size_t k=0; k < arr->length; k++) { |
| 100 | int p = arr->arr[k]; |
| 101 | if (p > limit) break; |
| 102 | if (i % p == 0) { |
| 103 | goto incr; |
| 104 | } |
| 105 | } |
| 106 | |
| 107 | printf("%llu\n", i); |
| 108 | if (uint64_array_append(arr, i)) { |
| 109 | goto error; |
| 110 | } |
| 111 | if (args.n > 0 && arr->length == args.n) { |
| 112 | break; |
| 113 | } |
| 114 | |
| 115 | incr: i += 1; |
| 116 | if (args.u > 0 && i > args.u) { |
| 117 | break; |
| 118 | } |
| 119 | } |
| 120 | end: |
| 121 | uint64_array_free(arr); |
| 122 | fflush(stdout); |
| 123 | return 0; |
| 124 | |
| 125 | error: |
| 126 | uint64_array_free(arr); |
| 127 | perror("Error"); |
| 128 | return 1; |
| 129 | } |