বৃহস্পতিবার, ১১ মে, ২০১৭

UVA 11287 - Pseudoprime Numbers

#include<bits/stdc++.h>
using namespace std;
long long isPrime(long long  x)
{
    long long i;
    for(i = 2; i*i <= x; i++)
        if(x%i == 0)
            return 0;
    return 1;
}
long long bigmod(long long bb,long long pp,long long m)
{
    if(bb==0) return 0;
    long long x,power;
    x=1;
    power=bb%m;
    while(pp)
    {
        if(pp%2==1)
            x=(x*power)%m;
        power=(power*power)%m;
        pp=pp/2;
    }
    return x;
}
main()
{
    long long a,b;
    while(cin>>a>>b)
    {
        if(a==0&&b==0)
            break;
        if(isPrime(a))
        {
            printf("no\n");
        }
        else
        {
            long long k=bigmod(b,a,a);
            if(k==b)
            {
                printf("yes\n");
            }
            else
                printf("no\n");
        }
    }
}

কোন মন্তব্য নেই:

একটি মন্তব্য পোস্ট করুন

Factorization with prime Sieve

vector <int> prime; char sieve[1000009]; int N=1000009; void primeSieve ( ) { sieve[0] = sieve[1] = 1; prime.push_back(2); ...