fork download
copy 
  1. #include <stdio.h>
  2. #include <stdint.h>
  3. #include <math.h>
  4.  
  5. #include <vector>
  6. #include <set>
  7. #include <algorithm>
  8.  
  9. auto prime_table(size_t N) {
  10.   std::vector<bool> table(N + 1, true);
  11.   auto sqrt_N = static_cast<size_t>(floor(sqrt(N) + 1));
  12.   table[0] = false;
  13.   table[1] = false;
  14.   printf("generating primes...\n");
  15.   for (size_t p = 2; p < sqrt_N; p++) {
  16.     if (table[p]) {
  17.       for (size_t k = p; k * p < table.size(); k++) {
  18.         table[k * p] = false;
  19.       }
  20.     }
  21.   }
  22.   return table;
  23. }
  24.  
  25. auto get_number(size_t x, size_t y, size_t N) {
  26.   auto X = ssize_t(x - (N - 1) / 2);
  27.   auto Y = ssize_t(y - N / 2);
  28.   auto mx = std::abs(X), my = std::abs(Y);
  29.   auto l = 2 * std::max(mx, my);
  30.   auto d = Y > X? l * 3 + X + Y: l - X - Y;
  31.   return static_cast<size_t>((l - 1) * (l - 1) + d);
  32. }
  33.  
  34. auto ulam_spiral() {
  35.   auto N = 10;
  36.   auto M = size_t(1) << N;
  37.   auto&& is_prime = prime_table(1 << N * 2);
  38.   std::vector<std::vector<bool>> buffer(M, std::vector<bool>(M, false));
  39.   printf("mapping to ulam-spiral...\n");
  40.   for (size_t x = 0; x < M; x++) {
  41.     for (size_t y = 0; y < M; y++) {
  42.       auto v = get_number(x, y, M);
  43.       if (is_prime[v]) {
  44.         buffer[x][y] = true;
  45.       }
  46.     }
  47.   }
  48.   printf("washing...\n");
  49.   std::vector<std::pair<size_t, size_t>> buffer2 = {{0, 0}};
  50.   while (!buffer2.empty()) {
  51.     auto pair = buffer2.back();
  52.     buffer2.pop_back();
  53.     auto x = pair.first, y = pair.second;
  54.     if (!buffer[x][y]) {
  55.       buffer[x][y] = true;
  56.       if (x != 0 && !buffer[x - 1][y]) {
  57.         buffer2.push_back(std::make_pair(x - 1, y));
  58.       }
  59.       if (x != M - 1 && !buffer[x + 1][y]) {
  60.         buffer2.push_back(std::make_pair(x + 1, y));
  61.       }
  62.       if (y != 0 && !buffer[x][y - 1]) {
  63.         buffer2.push_back(std::make_pair(x, y - 1));
  64.       }
  65.       if (y != M - 1 && !buffer[x][y + 1]) {
  66.         buffer2.push_back(std::make_pair(x, y + 1));
  67.       }
  68.     }
  69.   }
  70.   printf("detecting...\n");
  71.   auto n = 0;
  72.   for (size_t x = 1; x < M - 1; x++) {
  73.     for (size_t y = 1; y < M - 1; y++) {
  74.       if (!buffer[x][y]) {
  75.         if (!buffer[x + 1][y] || !buffer[x - 1][y] || !buffer[x][y - 1] || !buffer[x][y + 1]) {
  76.           printf("detected![%d] x = %zu, y = %zu, n = %zu\n", n, x, y, get_number(x, y, N));
  77.           n++;
  78.         }
  79.       }
  80.     }
  81.   }
  82.   return buffer;
  83. }
  84.  
  85. int main() {
  86.   auto&& table = ulam_spiral();
  87.   return 0;
  88. }
Success #stdin #stdout 0.08s 3744KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
generating primes...
mapping to ulam-spiral...
washing...
detecting...
https://ideone.com/C2FulF
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!