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:
{{trans|Wren}}
<syntaxhighlight lang="c">#include <stdio.h>
#include <stdbool.h>
#include <locale.h>
 
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 (countn >< 2) gotoreturn endfalse;▼
void primeFactors(int n, int *factors, int *length) {
intif count(n%2 == 0) return n == 2;
if (n%3 == 10) gotoreturn endn == 3;
whileint (!(n%3))d {= 5;
while (d*d <= n) {
factors[count++] = 3;
if (countn%d >== 20) gotoreturn endfalse;
nd /+= 32;
if (countn%d >== 20) gotoreturn endfalse;▼
}
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; ) {
if (!(n%k)) {
factors[count++] =return k;
▲ if (count > 2) goto end;
n /= k;▼
} else {
k += inc[i];
Line 55 ⟶ 59:
}
}
ifreturn (n > 1) {;
factors[count++] = n;
}
end:
*length = count;
}
 
int main() {
int i = 1, j, bc = 0, lengthp, = 0q;
int f[20], blum[50], counts[4] = {0}, digits[4] = {1, 3, 5, 7};
setlocale(LC_NUMERIC, "");
while (1true) {
primeFactors(i,p f,= &lengthfirstPrimeFactor(i);
if (length == 2 && f[0] != f[1] && f[0] % 4 == 3 && f[1]p % 4 == 3) {
ifq (bc= <i 50)/ blum[bc] = ip;
++counts[iif (q != p && q % 104 /== 3]; && isPrime(q)) {
++ if (bc < 50) blum[bc] = i;
if (bc == 50) {++counts[i % 10 / 3];
printf("First 50 Blum integers:\n")++bc;
forif (jbc = 0; j <= 50; ++j) {
printf("%3dFirst ",50 blum[j]Blum integers:\n");
iffor (!((j+1) %= 10))0; printf("\n")j < 50; ++j) {
} printf("%3d ", blum[j]);
if (!((j+1) % 10)) printf("\n");
} else if (bc == 26828 || !(bc % 100000)) {}
printf("The %'7dth Blum integer is: %'9dprintf("\n", bc, i);
} else if (bc == 40000026828 || !(bc % 100000)) {
printf("\n%The %'7dth distributionBlum ofinteger theis: first%'9d\n", 400bc,000 Blum integers:\n"i);
forif (jbc == 0; j < 4; ++j400000) {
printf(" %6.3f\n%% enddistribution inof %dthe first 400,000 Blum integers:\n", counts[j]/4000.0, digits[j]);
break for (j = 0; j < 4; ++j) {▼
printf(" %6.3f%% end in %d\n", counts[j]/4000.0, digits[j]);
▲ n /= k; }
break;
}
▲ break;
}
}
}
i += (i % 5 == 3) ? 4 : 2;
}
return 0;
}</syntaxhighlight>
Retrieved from "https://rosettacode.org/wiki/Blum_integer"