debianforum.de

factorize.c

SNIPPET_DESC:

Verbesserte Primzahlenfaktorisierung in C

SNIPPET_CREATION_TIME:

10.12.2023 12:40:48

SNIPPET_PRUNE_TIME:

Unendlich

SNIPPET_TEXT:

1. #include <math.h>
2. #include <stdbool.h>
3. #include <stdio.h>
4. #include <stdlib.h>
5. #include <string.h>
6.  
7. bool is_prime(int);
8. int *primes_up_to(int);
9. int *factorize(int);
10.  
11. int main(int argc, char *argv[])
12. {
13.     int lower = 0, upper = 0, i = 0, j = 0;
14.  
15.     if (argc < 3) {
16.         fprintf(stderr, "usage: %s lower upper\n", argv[0]);
17.         return 1;
18.     }
19.  
20.     lower = atoi(argv[1]);
21.     upper = atoi(argv[2]);
22.     if (lower > upper) {
23.         fprintf(stderr, "lower must be <= upper, was %d > %d\n", lower, upper);
24.         return 1;
25.     }
26.  
27.     for (i = lower; i <= upper; i++) {
28.         printf("%d: ", i);
29.         int *factors = factorize(i);
30.         for (j = 0; factors[j] != 0; j++) {
31.             printf("%d ", factors[j]);
32.         }
33.         free(factors);
34.         putchar('\n');
35.     }
36.  
37.     return 0;
38. }
39.  
40. int *factorize(int x)
41. {
42.     int i = 0, j = 0, n = 0;
43.     int *primes = NULL, *factors = NULL;
44.  
45.     if (x < 1) {
46.         factors = (int *)calloc(1, sizeof(int));
47.         return factors;
48.     }
49.  
50.     n = log2(x) + 1; // heuristic: log2(16) = 4, fits "worst" case  [2, 2, 2, 2]
51.     primes = primes_up_to(sqrt(x));
52.     factors = (int *)calloc(n, sizeof(int));
53.  
54.     for (i = 0, j = 0; primes[i] != 0 && x > 1;) {
55.         if (x % primes[i] == 0) {
56.             factors[j++] = primes[i];
57.             x /= primes[i];
58.         } else {
59.             i++;
60.         }
61.     }
62.     if (x > 1) {
63.         factors[j] = x;
64.     }
65.     free(primes);
66.  
67.     return factors;
68. }
69.  
70. int *primes_up_to(int x)
71. {
72.     int i = 0, j = 0, n = 0;
73.     int *primes = NULL;
74.  
75.     if (x < 2) {
76.         primes = (int *)calloc(1, sizeof(int));
77.         primes[0] = 0;
78.         return primes;
79.     }
80.  
81.     n = x / log10(x) + 1;
82.     primes = (int *)calloc(n, sizeof(int));
83.  
84.     for (i = 2, j = 0; i <= x; i++) {
85.         if (is_prime(i)) {
86.             primes[j++] = i;
87.         }
88.     }
89.  
90.     return primes;
91. }
92.  
93. bool is_prime(int x)
94. {
95.     if (x < 2) {
96.         return false;
97.     }
98.     for (int i = 2; i <= x / 2; i++) {
99.         if (x % i == 0) {
100.             return false;
101.         }
102.     }
103.     return true;
104. }

Quellcode

Hier kannst du den Code kopieren und ihn in deinen bevorzugten Editor einfügen. PASTEBIN_DOWNLOAD_SNIPPET_EXPLAIN