Prime conspiracy: Difference between revisions
→{{header|C++}}
Line 164:
9->9 42843 4.28
</pre>
=={{header|C}}==
{{trans|C++}}
<lang c>#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
typedef unsigned char byte;
struct Transition {
byte a, b;
unsigned int c;
} transitions[100];
void init() {
int i, j;
for (i = 0; i < 10; i++) {
for (j = 0; j < 10; j++) {
int idx = i * 10 + j;
transitions[idx].a = i;
transitions[idx].b = j;
transitions[idx].c = 0;
}
}
}
void record(int prev, int curr) {
byte pd = prev % 10;
byte cd = curr % 10;
int i;
for (i = 0; i < 100; i++) {
int z = 0;
if (transitions[i].a == pd) {
int t = 0;
if (transitions[i].b == cd) {
transitions[i].c++;
break;
}
}
}
}
void printTransitions(int limit, int last_prime) {
int i;
printf("%d primes, last prime considered: %d\n", limit, last_prime);
for (i = 0; i < 100; i++) {
if (transitions[i].c > 0) {
printf("%d->%d count: %5d frequency: %.2f\n", transitions[i].a, transitions[i].b, transitions[i].c, 100.0 * transitions[i].c / limit);
}
}
}
bool isPrime(int n) {
int s, t, a1, a2;
if (n % 2 == 0) return n == 2;
if (n % 3 == 0) return n == 3;
if (n % 5 == 0) return n == 5;
if (n % 7 == 0) return n == 7;
if (n % 11 == 0) return n == 11;
if (n % 13 == 0) return n == 13;
if (n % 17 == 0) return n == 17;
if (n % 19 == 0) return n == 19;
// assuming that addition is faster then multiplication
t = 23;
a1 = 96;
a2 = 216;
s = t * t;
while (s <= n) {
if (n % t == 0) return false;
// first increment
s += a1;
t += 2;
a1 += 24;
assert(t * t == s);
if (s <= n) {
if (n % t == 0) return false;
// second increment
s += a2;
t += 4;
a2 += 48;
assert(t * t == s);
}
}
return true;
}
#define LIMIT 1000000
int main() {
int last_prime = 3, n = 5, count = 2;
init();
record(2, 3);
while (count < LIMIT) {
if (isPrime(n)) {
record(last_prime, n);
last_prime = n;
count++;
}
n += 2;
if (count < LIMIT) {
if (isPrime(n)) {
record(last_prime, n);
last_prime = n;
count++;
}
n += 4;
}
}
printTransitions(LIMIT, last_prime);
return 0;
}</lang>
{{out}}
<pre>1000000 primes, last prime considered: 15485863
1->1 count: 42853 frequency: 4.29
1->3 count: 77475 frequency: 7.75
1->7 count: 79453 frequency: 7.95
1->9 count: 50153 frequency: 5.02
2->3 count: 1 frequency: 0.00
3->1 count: 58255 frequency: 5.83
3->3 count: 39668 frequency: 3.97
3->5 count: 1 frequency: 0.00
3->7 count: 72827 frequency: 7.28
3->9 count: 79358 frequency: 7.94
5->7 count: 1 frequency: 0.00
7->1 count: 64230 frequency: 6.42
7->3 count: 68595 frequency: 6.86
7->7 count: 39603 frequency: 3.96
7->9 count: 77586 frequency: 7.76
9->1 count: 84596 frequency: 8.46
9->3 count: 64371 frequency: 6.44
9->7 count: 58130 frequency: 5.81
9->9 count: 42843 frequency: 4.28</pre>
=={{header|C++}}==
| |||