#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>

int gcd(unsigned long a,unsigned long b);
int Is_Prime(unsigned int p);
unsigned power(unsigned a,unsigned b,unsigned long c);



main()
{
    unsigned int p=10,q=10;
    unsigned long n;

    srand(time(NULL));


    while(!Is_Prime(p))
    p=50000+rand()%10000;
    while(!Is_Prime(q))
    q=10000+rand()%55535;
    n=(unsigned long)p*(unsigned long)q;

    printf("p= %u\n",p);
    printf("q= %u\n",q);
    printf("n= %lu\n-------------------\n",n);

    getchar();
    printf("%d\n",Is_Prime(47));
     getchar();
}

int gcd(unsigned long a,unsigned long b)
{
 unsigned long x,y,r ;  x=a; y=b;
 while(1){
 if(y==0)
    return 0;
 if(y==1)
    return 1;
 r=x%y;
 x=y;
 y=r;}
}

int Is_Prime(unsigned int p)
{
    int i;

    for(i=2;i<sqrt(p);i++)
        if((p%i)==0)
            return 0;

    return 1;
}


unsigned power(unsigned a,unsigned b,unsigned long c)
{
 /*此函數計算"a的b次方對c求余"*/

 unsigned long z=1,t;
 for(t=a;b>0;b>>=1)
 {
  /*每輪循環b右移1位是為了控制循環次數,可如下等價理解:*/
  /*將b寫成二進制形式:mk,mk-1,mk-2------m0.其中k就是循環次數*/

  /* 在以下的注釋中: "a(mk)"代表"a的mk次方","(a)(b)"代表"a的b次方",*/
  /* "[a]*[b]"代表"a*b"*/

  /* 此函數的原理是:*/
  /* b寫成二進制形式后,"a的b次方"=a(b)=[(a(mk))(2(k))]*[(a(mk-1))(2(k-1))]*   */
  /* [(a(mk-2))(2(k-2))]----*[(a(m0))(2(0))].由此可見mi=0的項的值=1,因此這一項*/
  /* 不用累乘到"a的b次方"中,只有當mi=1時,才將[(a(mi))(2(i))]累乘到"a的b次方"中*/

   if(b%2==1)z=(z*t)%c;  /*z用來存放當前的"a的b次方"*/

   /* "b%2==1"說明b是奇數.當b是奇數時,b的二進制表示的最低位是1.又因為每次循環b*/
   /* 都右移1位,因此此時b的最低位其實是傳入此函數的b的二進制表示的第j位*/
   /* j表示當前的循環次數,從0開始,二進制表示的位數從0開始. */

   /*對于傳入此函數的b, 若其二進制表示第j位為1,即mj=1,則根據上面提到的此函數的*/
   /*原理,應將mj,mj-1,mj-2-------m0表示的十進制數(即[(a(mj))(2(j))])累乘到z中*/
   /*而[(a(mj))(2(j))]就是t*/

   t=(t*t)%c;

   /* 此函數實際操作時:*/
   /* t存放當前"a的i次方"的值(i=1,2,3----k)*/
   /* [(a(m))(2(i))]的值*/

  }
  return z;
 }