// Program to calculate Legendre Symbol

#include <iostream>

using namespace std;

int legendre(int x,int p)
{ // finds (x/p) as 1 or -1
	int m,k,p8,t,u4;
  
	m=0;
	while(p>1)
	{ /* main loop */
// extract powers of 2
		for (k=0;x%2==0;k++) x/=2;
		p8=p%8;
		if (k%2==1) m+=(p8*p8-1)/8;

// quadratic reciprocity 

        m+=((p8-1)*(x%4-1))/4;
        t=p;  t%=x;
        p=x;  x=t;
        m%=2;

	}
	if (m==0) return 1;
	else      return (-1);
} 

int main()
{
    int lg,x,p;

    x=40902;
    p=84143;

    lg=legendre(x,p);
    cout << "legendre symbol= " << lg << endl;

}