SwiftyNote

主にSwiftな技術ブログ

【ガウス素数】読ませる気のないアルゴリズムシリーズ【第一弾】

自分の中では一番得意な言語であるC/C++言語。業務ではSwiftの内部実装を見る以外に使うことはないので日に日に忘れていってしまいそうである。なのでC++を思い出しつつ、なにかテーマを探し記事としてまとめることで実装力とアルゴリズム力を維持するための1人企画である。 本シリーズは自分用のため、読ませる気はないのでご了承くださいm( )m 絶対に業務では書かないような記法、実装が多々あるためご注意ください。しかし、最低限の処理だけで書きコピペで動作確認できるようなものにしたいと思いますので、奇跡的に学習したいテーマのアルゴリズムだった。などというパターンのみご利用ください。あまり有名なものはチョイスしない方針です。

ガウス素数とは

Wikipediaなどを調べても、ん?となるだけだ。どんなに複雑で難解な説明でもアルゴリズムとその使いみちがわかるほうが数倍重要だと思う。 つまり、ガウス素数は左右対称なきれいな模様を導ける素数とだけ覚えておいたほうが今後役に立つはずだ。(実際にはちゃんと説明は読んだ) 実際にガウス素数の説明には

テーブルクロス織りにも用いられることもある。

と書いてある。もしかしたらカラーグラデーションなどにも応用できるかもしれない。これは期待できる。 早速実装してみよう。

実装

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 27;
char a[N+1][N+1];
int main() {
    int q,p,x,y;
    const int SN = sqrt(N);
    fill(&a[0][0],&a[N][0]+N,1);
    a[0][0] = a[1][0] = a[0][1] = 0;
    for(int i=0;i<SN;i++){
        for(int j=0;j<=i;j++){
            if(!a[i][j])continue;
            p=i;q=j;
            while(p<=N){
                x=p;y=q;
                do{
                    a[x][y]=a[y][x]=0;
                }while ((x-=j)>=0 && (y+=i)<=N);
                x=p;y=q;
                do{
                    a[x][y]=a[y][x]=0;
                }while ((x+=j)<=N && (y-=i)>=0);
                p+=i;q+=j;
            }
            a[i][j]=a[j][i]=1;
        }
    }
    for(int i=-N;i<=N;i++){
        for(int j=-N;j<=N;j++){
                printf("%s",(a[abs(i)][abs(j)] && i*i+j*j<=N*N)?"■■":"  ");
        }
        cout<<endl;
    }
}

実行結果:

                          ■■                          
                ■■  ■■          ■■  ■■                
              ■■  ■■      ■■      ■■  ■■              
            ■■      ■■  ■■  ■■  ■■      ■■            
              ■■  ■■      ■■      ■■  ■■              
            ■■  ■■  ■■          ■■  ■■  ■■            
      ■■  ■■          ■■  ■■  ■■          ■■  ■■      
    ■■  ■■      ■■      ■■  ■■      ■■      ■■  ■■    
  ■■      ■■  ■■  ■■  ■■      ■■  ■■  ■■  ■■      ■■  
    ■■  ■■      ■■      ■■  ■■      ■■      ■■  ■■    
  ■■  ■■  ■■          ■■  ■■  ■■          ■■  ■■  ■■  
            ■■  ■■  ■■  ■■  ■■  ■■  ■■  ■■            
      ■■      ■■  ■■  ■■■■  ■■■■  ■■  ■■      ■■      
■■  ■■  ■■  ■■      ■■          ■■      ■■  ■■  ■■  ■■
      ■■      ■■  ■■  ■■■■  ■■■■  ■■  ■■      ■■      
            ■■  ■■  ■■  ■■  ■■  ■■  ■■  ■■            
  ■■  ■■  ■■          ■■  ■■  ■■          ■■  ■■  ■■  
    ■■  ■■      ■■      ■■  ■■      ■■      ■■  ■■    
  ■■      ■■  ■■  ■■  ■■      ■■  ■■  ■■  ■■      ■■  
    ■■  ■■      ■■      ■■  ■■      ■■      ■■  ■■    
      ■■  ■■          ■■  ■■  ■■          ■■  ■■      
            ■■  ■■  ■■          ■■  ■■  ■■            
              ■■  ■■      ■■      ■■  ■■              
            ■■      ■■  ■■  ■■  ■■      ■■            
              ■■  ■■      ■■      ■■  ■■              
                ■■  ■■          ■■  ■■                
                          ■■                       

なるほど? 使いみちがわからない。

ガウス整数 - Wikipedia