这是一个入门的数论题目 ， 只需要简单的找素数和快速幂取模

题意：输入一个数 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<