uva 10006 數論入門題

這是一個入門的數論題目 ， 只需要簡單的找素數和快速冪取模

題意：輸入一個數 n ， 如果這個數是非素數 ， 問是不是 這個2~n-1區間的所有數都滿足 ？

解法：由於數據量不大 ， 可以直接暴力求解

解法1： 暴力求解

#include 
#include 
#include 

using namespace std;

long long prime[65010];
long long n;


void init()
{
    memset(prime , 0 , sizeof(prime));
    long long i , j;

    for(i = 2; i < 65000 ; i++)
    {
        if(prime[i] == 0)
        {
            for(j = i+i; j < 65000; j += i)
                prime[j] = 1;
        }
    }
}

long long pow_mod(long long a)
{
    long long x = 1 , y = a;
    long long z = n;
    while(z-1)
    {
        if(z%2 == 1)
            x = x*y%n;
        y = y*y%n;
        z /= 2;
    }
    x = x*y%n;
    return x;
}

int main()
{
    init();
    while(1)
    {
        long long i ;
        cin>>n;
        if(n == 0)  break;
        if(!prime[n])
        {
            cout<

解法2：

利用唯一分解定理 ，  任何一個非素數 ， 都會由素數因子組成 ， 因此當我們要求 a^n 時 ，
我們通過 a = x*y  ,   a^n = (x^n)*(y^n) ， 這時我們就只需求得 a 的一個因子 ， 由此可以降低時間復雜度
#include 
#include 
#include 

using namespace std;

int prime[65010];
long long n;
long long gcd[65010];
long long pri[65010];

void init()
{
    memset(prime , 0 , sizeof(prime));
    long long i , j;

    for(i = 2; i < 65000 ; i++)
    {
        if(prime[i] == 0)
        {
            for(j = i+i; j < 65000; j += i)
                prime[j] = 1 , pri[j] = i;
        }
    }
}

long long pow_mod(long long a)
{
    long long x = 1 , y = a;
    long long z = n;
    while(z-1)
    {

        if(z%2 == 1)
            x = x*y%n;
        y = y*y%n;
        z /= 2;
    }
    x = x*y%n;
    return x;
}

int main()
{
    init();
    while(1)
    {
        long long i , j , x;
        cin>>n;
        if(n == 0)  break;
        if(!prime[n])
        {
            cout<