86 lines
1.7 KiB
C
86 lines
1.7 KiB
C
#include <stdint.h>
|
|
#include <stdio.h>
|
|
#include <assert.h>
|
|
#include <inttypes.h>
|
|
#include <string.h>
|
|
#include <math.h>
|
|
#include <stdbool.h>
|
|
|
|
static inline int hamming_distance(uint32_t x, uint32_t y)
|
|
{
|
|
uint32_t val = x ^ y;
|
|
return __builtin_popcount(val);
|
|
}
|
|
|
|
uint32_t print_list(uint32_t * nums, int len)
|
|
{
|
|
for (uint32_t i = 0; i < len; i++) {
|
|
printf("0x%06" PRIx32 ", ", nums[i]);
|
|
}
|
|
printf("\n");
|
|
}
|
|
|
|
static const int target = 14;
|
|
|
|
bool is_prime(int num) {
|
|
if (num <= 1) return false;
|
|
if (num <= 3) return true;
|
|
|
|
int range = sqrt(num);
|
|
// This is checked so that we can skip
|
|
// middle five numbers in below loop
|
|
if (num % 2 == 0 || num % 3 == 0)
|
|
return false;
|
|
|
|
for (int i = 5; i <= range; i += 6)
|
|
if (num % i == 0 || num % (i + 2) == 0)
|
|
return false;
|
|
|
|
return true;
|
|
}
|
|
|
|
static uint32_t primes[1 << 24];
|
|
static int primes_length = 0;
|
|
|
|
int foo(uint32_t * nums, int len)
|
|
{
|
|
uint32_t nums1[len + 1];
|
|
|
|
for (uint32_t j = 0xaaaaaa; j > 1; j--) {
|
|
if (__builtin_popcount(j) > 12 || __builtin_popcount(j) < 8) continue;
|
|
for (int i = 0; i < len; i++) {
|
|
if (hamming_distance(nums[i], j) < target) {
|
|
goto next_n;
|
|
}
|
|
}
|
|
|
|
memcpy(nums1, nums, (sizeof (uint32_t)) * len);
|
|
nums1[len] = j;
|
|
if (len + 1 >= 6) {
|
|
print_list(&nums1[0], len + 1);
|
|
return 1;
|
|
}
|
|
|
|
if (len < 6) {
|
|
int n = foo(&nums1[0], len + 1);
|
|
}
|
|
|
|
next_n:
|
|
continue;
|
|
}
|
|
|
|
return 0;
|
|
}
|
|
|
|
int main()
|
|
{
|
|
for (uint32_t j = 0xaaaaaa; j > 1; j--) {
|
|
if (__builtin_popcount(j) > 12 || __builtin_popcount(j) < 8) continue;
|
|
if (!is_prime(j)) continue;
|
|
primes[primes_length++] = j;
|
|
}
|
|
printf("%d\n", primes_length);
|
|
|
|
foo(NULL, 0);
|
|
}
|