#include <stdio.h>
#include <iostream>
#include <complex>
#include <string.h>
#include <stdlib.h>




// ANMERKUNGEN:
// einheiten sind 1,i,-1,-i
// ist a+bi prim, so ist auch a-bi prim
// ist z=a+bi prim, so sind auch -z,iz,-iz und damit auch z~,-z~,iz~,-iz~ prim
// ist a+bi prim, so ist auch b+ai prim

// reelle spezialfaelle: 4k+1 (sind nie prim) und 4k+3 (sind immer prim)
// z=a+bi ist prim, wenn: (1) { a=0 und b=(4k+3)prim } (2) { a!=0 und b!=0 } und  { a^2+b^2 ist prim oder a^2+b^2=prim^2 }
//http://en.wikipedia.org/wiki/Gaussian_integer



using namespace std;

int  IsInt(double dzahl);
int  test(complex<double> czahl);
bool test2(complex<double> zahl);
bool k_test(float zahl);
bool p_test(float zahl);

// definiere die einheiten und die null
complex<double> einheit_1 (1,0);
complex<double> einheit_2 (0,1);
complex<double> einheit_3 (-1,0);
complex<double> einheit_4 (0,-1);
complex<double> null (0,0);



int main (int argc, char *argv[])
{

  // prüfe, ob ein argument angegeben wurde
  if(argc < 2)
  {
		printf("Brauche ganzzahliges Argument n:\nEs werden dann Primzahlen von -n-ni bis n+ni gesucht\n");
		return -1;
  }
  
  
  // lege die maximale größe der zu suchenden primzahl fest
  double rmax = atof(argv[1]);
  

  
  // gebe die ersten, trivialen primzahlen gleich aus
  cout << "1" << " "<<"1"<< endl;
  cout << "1" << " "<<"-1"<< endl;
  cout << "-1" << " "<<"1"<< endl;
  cout << "-1" << " "<<"-1"<< endl;


  // erzeuge zu prüfende komplexe zahlen
  // erstmal den reellen teil von null bis rmax
  
  int r,i;
  
  
  for( int r = 0; r <= rmax; r++ )
  {
      // dann den imaginärteil von 0 bis r, alle anderen primzahlen ergeben sich aus symmetriegründen
      
      for( int i = 0; i < r; i++ )
      {

		// gerade zahlen müssen nicht getesten werden ( null ist inklusive )
		if ( r%2 == 0 && i%2 == 0 )	
			continue;

		// erstelle die zu prüfende komplexe zahl
		complex<double> zahl (r,i);
	
		
		// die einheiten müssen nicht getestet werden, sie sind per definition nicht prim
		if( zahl == einheit_1 || zahl == einheit_2 || zahl == einheit_3 || zahl == einheit_4 )
			continue;

		// teste zahl auf prim	
		if( test2(zahl) == true )
		{
			// getestete zahl a+bi ist prim
	  		cout << real(zahl) << " "<<imag(zahl)<< endl;
	

			// wenn die zahl prim ist, ist auch die multiplikation mit den elementen prim
			cout << real(zahl*einheit_2) << " "<<imag(zahl*einheit_2)<< endl;
			cout << real(zahl*einheit_3) << " "<<imag(zahl*einheit_3)<< endl;
			cout << real(zahl*einheit_4) << " "<<imag(zahl*einheit_4)<< endl;

			// und damit sind dann auch b+ai und deren produkte mit den einheiten prim
			cout << imag(zahl) << " "<<real(zahl)<< endl;

			cout << imag(zahl*einheit_2) << " "<<real(zahl*einheit_2)<< endl;
			cout << imag(zahl*einheit_3) << " "<<real(zahl*einheit_3)<< endl;
			cout << imag(zahl*einheit_4) << " "<<real(zahl*einheit_4)<< endl;


			
 		}
	
      }
    
    
  }
  
  
  
  
  return 1;
  
} 



int IsInt(double dzahl)
{// prüft, ob eine (reelle) zahl ganzzahlig ist (auch 1.0 wird als Ganzzahl interpretiert)
  
	double intpart;

	double trunk = modf(dzahl,&intpart);

	if( trunk == 0. )
		return 1;
	else
	{
		return 0;
	}

  
}


bool test2(complex<double> zahl)
{// testet, ob ein element aus C prim ist
 // methode: prüfe ob norm prim ist

	int re = real(zahl);
	int im = imag(zahl);
	

	// erstmal die spezialfaelle abarbeiten: re=0 oder im=0
	// wenn nämlich re oder im eine 4k+3 primzahl sind, dann ist die komplexe zahl prim
	if( re == 0 && im != 0)
	{
		if( k_test(im) == 1 )
			return 1;
		else
			return 0;
	}
	

	if( im == 0 && re != 0)
	{
		if( k_test(re) == 1 )
			return 1;
		else
			return 0;
	}
	

	
	int norm = re*re + im*im; // immer ganzzahlig, weil re und im ganzzahlig
	

	// ist die norm (rationale) prim, so ist auch die komplexe zahl prim
	if( p_test(norm) )
	{
		return 1;
	}


	// ist die norm das quadrat einer (rationale) primzahl, so ist auch die komplexe zahl prim
	if( k_test(sqrt(norm)) )
	{
		return 1;
	}

	return 0;

}


bool k_test(float zahl)
{// testet, ob zahl eine 4k+3 primzahl ist

	// normaler primtest
	if( !p_test(zahl) )
		return 0;

	// wir kommen bis hier, wenns ne primzahl ist

	// prüfen, obs auch ne 4k+3 primzahl ist:

	for( int k=0; k<= (zahl/4); k++ )
	{
		if( (4*k+3) == zahl )
		{
			return 1;
		}

	}


	return 0;

}


bool p_test(float zahl)
{// testet eine zahl aus IR auf prim

	// nicht ganze zahlen müssen nicht getestet werden
	if( !IsInt(zahl) )
	{	
		return 0;
	}

	
	// teste auf prim
	for(int j=2;j<=sqrt(zahl);j++)
	{

		if( int(zahl)%j == 0 )
		{
			return 0;
			
		}

	}


	return 1;

}