Blum integer: Difference between revisions

Content added Content deleted
(→‎{{header|Wren}}: Optimized - about 30% faster than before.)
(→‎{{header|C}}: Updated in line with Wren example - run time now under 1 second.)
Line 27: Line 27:
{{trans|Wren}}
{{trans|Wren}}
<syntaxhighlight lang="c">#include <stdio.h>
<syntaxhighlight lang="c">#include <stdio.h>
#include <stdbool.h>
#include <locale.h>
#include <locale.h>


int inc[8] = {4, 2, 4, 2, 4, 6, 2, 6};
int inc[8] = {4, 2, 4, 2, 4, 6, 2, 6};


bool isPrime(int n) {
// Assumes n is odd and bails out when factor count exceeds 2.
⚫
if (n < 2) return false;
void primeFactors(int n, int *factors, int *length) {
int count = 0;
if (n%2 == 0) return n == 2;
if (n == 1) goto end;
if (n%3 == 0) return n == 3;
while (!(n%3)) {
int d = 5;
while (d*d <= n) {
factors[count++] = 3;
if (count > 2) goto end;
if (n%d == 0) return false;
n /= 3;
d += 2;
⚫
if (n%d == 0) return false;
}
while (!(n%5)) {
d += 4;
factors[count++] = 5;
⚫
if (count > 2) goto end;
n /= 5;
}
}
return true;
}

// Assumes n is odd.
int firstPrimeFactor(int n) {
if (n == 1) return 1;
if (!(n%3)) return 3;
if (!(n%5)) return 5;
for (int k = 7, i = 0; k*k <= n; ) {
for (int k = 7, i = 0; k*k <= n; ) {
if (!(n%k)) {
if (!(n%k)) {
factors[count++] = k;
return k;
⚫
if (count > 2) goto end;
⚫
n /= k;
} else {
} else {
k += inc[i];
k += inc[i];
Line 55: Line 59:
}
}
}
}
if (n > 1) {
return n;
factors[count++] = n;
}
end:
*length = count;
}
}


int main() {
int main() {
int i = 1, j, bc = 0, length = 0;
int i = 1, j, bc = 0, p, q;
int f[20], blum[50], counts[4] = {0}, digits[4] = {1, 3, 5, 7};
int blum[50], counts[4] = {0}, digits[4] = {1, 3, 5, 7};
setlocale(LC_NUMERIC, "");
setlocale(LC_NUMERIC, "");
while (1) {
while (true) {
primeFactors(i, f, &length);
p = firstPrimeFactor(i);
if (length == 2 && f[0] != f[1] && f[0] % 4 == 3 && f[1] % 4 == 3) {
if (p % 4 == 3) {
if (bc < 50) blum[bc] = i;
q = i / p;
++counts[i % 10 / 3];
if (q != p && q % 4 == 3 && isPrime(q)) {
++bc;
if (bc < 50) blum[bc] = i;
if (bc == 50) {
++counts[i % 10 / 3];
printf("First 50 Blum integers:\n");
++bc;
for (j = 0; j < 50; ++j) {
if (bc == 50) {
printf("%3d ", blum[j]);
printf("First 50 Blum integers:\n");
if (!((j+1) % 10)) printf("\n");
for (j = 0; j < 50; ++j) {
}
printf("%3d ", blum[j]);
printf("\n");
if (!((j+1) % 10)) printf("\n");
} else if (bc == 26828 || !(bc % 100000)) {
}
printf("The %'7dth Blum integer is: %'9d\n", bc, i);
printf("\n");
if (bc == 400000) {
} else if (bc == 26828 || !(bc % 100000)) {
printf("\n%% distribution of the first 400,000 Blum integers:\n");
printf("The %'7dth Blum integer is: %'9d\n", bc, i);
for (j = 0; j < 4; ++j) {
if (bc == 400000) {
printf(" %6.3f%% end in %d\n", counts[j]/4000.0, digits[j]);
printf("\n%% distribution of the first 400,000 Blum integers:\n");
⚫
for (j = 0; j < 4; ++j) {
printf(" %6.3f%% end in %d\n", counts[j]/4000.0, digits[j]);
⚫
}
break;
}
}
⚫
break;
}
}
}
}
}
}
i += (i % 5 == 3) ? 4 : 2;
i += (i % 5 == 3) ? 4 : 2;
}
}
return 0;
return 0;
}</syntaxhighlight>
}</syntaxhighlight>
Retrieved from "https://rosettacode.org/wiki/Blum_integer"