费马小定理(Fermat Theory)
是数论中的一个重要定理,其内容为:
假如p是质数,且gcd(a,p)=1,那么 a(p-1)≡1(mod p)。即:假如a是整数,p是质数,且a,p互质(即两者只有一个公约数1),那么a的(p-1)次方除以p的余数恒等于1。
a^(p-1)%p=1
(其中%为取模操作,且a<p,p为质数)
费马小定理是初等数论四大定理(威尔逊定理,欧拉定理(数论中的欧拉定理),中国剩余定理(又称孙子定理)之一,在初等数论中有着非常广泛和重要的应用。实际上,它是欧拉定理的一个特殊情况(即
,见于词条“欧拉函数”)。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<ctime> 6 #define ll long long int//能够直接使用long long 7 8 using namespace std; 9 10 ll n; 11 ll pd[14]={10,35,77,535,71497,2,3,5,7,11,3161}; 12 ll fastmul(ll a,ll b) 13 { 14 ll r=0; 15 ll base=a; 16 while(b!=0) 17 { 18 if(b%2!=0) 19 { 20 b--; 21 r=(r+base)%n; 22 } 23 b=b/2; 24 base=(base+base)%n; 25 } 26 return r%n; 27 } 28 ll fastpow(ll a,ll b) 29 { 30 ll r=1; 31 ll base=a; 32 while(b!=0) 33 { 34 if(b%2!=0) 35 r=fastmul(r,base)%n; 36 base=fastmul(base,base)%n; 37 b=b/2; 38 } 39 return r%n; 40 } 41 ll check(ll n) 42 { 43 if(n==2) return 1; 44 if(n<2&&(n%2==0)) return 0; 45 for(ll i=0;i<11;i++) 46 { 47 ll x=pd[i];//进行特判 48 if(x%n==0) 49 continue;//继续往下判断循环条件执行语句 50 ll ans=fastpow(x,n-1)%n; 51 if(ans!=1) 52 return 0; 53 } 54 return 1; 55 } 56 int main() 57 { 58 //srand(time(0)); 59 //scanf("%lld",&n); 60 cin>>n; 61 for(int i=1;i<=n;i++) 62 { 63 if(check(i)) printf("%d ",i); 64 } 65 return 0; 66 }