神奇的质数：4567, 124567, 3214567, 23456789, 55566677, 1234567894987654321, 11111111111111111111111，20170807，19970227，19980227……
关于质数的小知识：
1.质数的个数无限多（不存在最大的质数素）
证明：反证法，假设存在最大的质数P，那么我们可以构造一个新的数2 * 3 * 5 * 7 *… *P + 1（所有的质数乘起来加1）。显然这个数不能被任一质数整除（所有质数除它都余1），这说明我们找到了一个更大的质数。
存在任意长的一段连续数，其中的所有数都是合数（相邻素数之间的间隔任意大）
证明：当0<a<=n时，n!+a能被a整除。长度为n-1的数列n!+2, n!+3, n!+4, …, n!+n中，所有的数都是合数。这个结论对所有大于1的整数n都成立，而n可以取到任意大。所有大于2的素数都可以唯一地表示成两个平方数之差。
证明：大于2的素数都是奇数。假设这个数是2n+1。
由于(n+1)2=n2+2n+1，(n+1)2和n2就是我们要找的两个平方数。即：(n+1)2-n2=2n+1
下面证明这个方案是唯一的。如果素数p能表示成a2-b2，则p=a2-b2=(a+b)(a-b)。由于p是素数，那么只可能a+b=p且a-b=1，这给出了a和b的唯一解。当n为大于2的整数时，2n+1和2n-1两个数中，如果其中一个数是素数，那么另一个数一定是合数。
证明：2n不能被3整除。如果它被3除余1，那么2n-1就能被3整除；如果被3除余2，那么2n+1就能被3整除。总之，2n+1和2^n-1中至少有一个是合数。
Carmichael数:
1729=7*13*19
294409=37*73*109
56052361=211*421*631
118901521=271*541*811
172947529=307*613*919
216821881=331*661*991
228842209=337*673*1009
1299963601=601*1201*1801
2301745249=727*1453*2179
9624742921=1171*2341*3511
11346205609=1237*2473*3709
13079177569=1297*2593*3889
21515221081=1531*3061*4591
27278026129=1657*3313*4969
65700513721=2221*4441*6661
71171308081=2281*4561*6841
100264053529=2557*5113*7669
168003672409=3037*6073*9109
172018713961=3061*6121*9181
173032371289=3067*6133*9199
464052305161=4261*8521*12781
527519713969=4447*8893*13339
663805468801=4801*9601*14401
727993807201=4951*9901*14851
856666552249=5227*10453*15679
1042789205881=5581*11161*16741
1201586232601=5851*11701*17551
1396066334401=6151*12301*18451
1544001719761=6361*12721*19081
1797002211241=6691*13381*20071
1920595706641=6841*13681*20521
2028691238689=6967*13933*20899
2655343122121=7621*15241*22861
2718557844481=7681*15361*23041
2724933935809=7687*15373*23059
2920883888089=7867*15733*23599
3091175755489=8017*16033*24049
3267961077889=8167*16333*24499
3296857440241=8191*16381*24571
3414146271409=8287*16573*24859
3711619793521=8521*17041*25561
3719466204049=8527*17053*25579
3878725359169=8647*17293*25939
4287981117241=8941*17881*26821
4507445537641=9091*18181*27271
6323547512449=10177*20353*30529
7622722964881=10831*21661*32491
8544361005001=11251*22501*33751
8681793690961=11311*22621*33931
9332984447209=11587*23173*34759
11004252611041=12241*24481*36721
11413778221441=12391*24781*37171
11765530852489=12517*25033*37549
13633039686169=13147*26293*39439
14470947115561=13411*26821*40231
14685655594249=13477*26953*40429
14882678745409=13537*27073*40609
15181505298649=13627*27253*40879
17167430884969=14197*28393*42589
18483957064801=14551*29101*43651
20742413217121=15121*30241*45361
21873528379441=15391*30781*46171
22027380041449=15427*30853*46279
24285059687809=15937*31873*47809
24977268314209=16087*32173*48259
25825129162489=16267*32533*48799
30833142247729=17257*34513*51769
33614369156161=17761*35521*53281
35700127755121=18121*36241*54361
37686301288201=18451*36901*55351
39782913594409=18787*37573*56359
48336382727569=20047*40093*60139
53269464581929=20707*41413*62119
57060521336809=21187*42373*63559
58774132848169=21397*42793*64189
62303597046289=21817*43633*65449
67858397221969=22447*44893*67339
70895483772049=22777*45553*68329
73103085605161=23011*46021*69031
77833567590769=23497*46993*70489
81159260227849=23827*47653*71479
81466208375329=23857*47713*71569
86483161466209=24337*48673*73009
91968282854641=24841*49681*74521
95682503446921=25171*50341*75511
98445661027561=25411*50821*76231
105950928237841=26041*52081*78121
112374872517529=26557*53113*79669
118895125737961=27061*54121*81181
118974229155289=27067*54133*81199
122570307044209=27337*54673*82009
127393969917241=27691*55381*83071
129140929242289=27817*55633*83449
137243534644009=28387*56773*85159
168011973623089=30367*60733*91099
177548395641481=30931*61861*92791
184455452572849=31327*62653*93979
192410140250521=31771*63541*95311
195809339861929=31957*63913*95869
201375886537729=32257*64513*96769
221568419989801=33301*66601*99901
224093003069449=33427*66853*100279
225301895806609=33487*66973*100459
233141908767121=33871*67741*101611
251703127095769=34747*69493*104239
262815637149001=35251*70501*105751
280790932830409=36037*72073*108109
312790579286329=37357*74713*112069
318705390188641=37591*75181*112771
351025246957321=38821*77641*116461
381144706349401=39901*79801*119701
382177291511809=39937*79873*119809
387194417159761=40111*80221*120331
390854788519609=40237*80473*120709
413847154073161=41011*82021*123031
415848433183849=41077*82153*123229
428549255564041=41491*82981*124471
439801455648601=41851*83701*125551
440937387145009=41887*83773*125659
457240489374169=42397*84793*127189
482944146230449=43177*86353*129529
501291932351689=43717*87433*131149
510637565929609=43987*87973*131959
548962252005961=45061*90121*135181
566692953864841=45541*91081*136621
572536569523969=45697*91393*137089
601192212565969=46447*92893*139339
621214363151929=46957*93913*140869
629346067180561=47161*94321*141481
657623122439329=47857*95713*143569
667316922191641=48091*96181*144271
683938014196609=48487*96973*145459
701865606427129=48907*97813*146719
726693182050249=49477*98953*148429
742403294138881=49831*99661*149491
779475417411169=50647*101293*151939
787536877909321=50821*101641*152461
795934611306001=51001*102001*153001
806090432846689=51217*102433*153649
839110734385129=51907*103813*155719
847577589374881=52081*104161*156241
883519506462529=52807*105613*158419
913671191480401=53401*106801*160201
920153949774049=53527*107053*160579
921392227198801=53551*107101*160651
937277770955329=53857*107713*161569
938531360353681=53881*107761*161641
938844932257009=53887*107773*161659
952711345022401=54151*108301*162451
959377262271049=54277*108553*162829
1004612946644089=55117*110233*165349
1061085945064681=56131*112261*168391
1146654351705601=57601*115201*172801
1161408537694369=57847*115693*173539
1174103262876529=58057*116113*174169
1205317701684289=58567*117133*175699
1238966116844329=59107*118213*177319
1253739456971641=59341*118681*178021
1288666276813009=59887*119773*179659
1339280649331561=60661*121321*181981
1343656902505249=60727*121453*182179
1349240453427961=60811*121621*182431
1410449244539689=61717*123433*185149
1429041795997609=61987*123973*185959
1498183378245721=62971*125941*188911
1687660433615521=65521*131041*196561
1713289208592601=65851*131701*197551
1746281192537521=66271*132541*198811
1753405565279761=66361*132721*199081
1870541589252529=67807*135613*203419
1882982959757929=67957*135913*203869
1905516221350249=68227*136453*204679
1912563054372961=68311*136621*204931
2031356908867969=69697*139393*209089
2057172011015041=69991*139981*209971
2070426828700441=70141*140281*210421
2075744656861201=70201*140401*210601
2078939720299609=70237*140473*210709
2173577642709409=71287*142573*213859
2187327342530809=71437*142873*214309
2242345598524081=72031*144061*216091
2362089119838841=73291*146581*219871
2379535602228721=73471*146941*220411
2408803612382521=73771*147541*221311
2489624653085209=74587*149173*223759
2516759613761329=74857*149713*224569
2779587596043649=77377*154753*232129
2860540798515121=78121*156241*234361
2887649314391089=78367*156733*235099
2906926685502841=78541*157081*235621
3046337392794049=79777*159553*239329
3328900397368921=82171*164341*246511
3380206940558641=82591*165181*247771
3410501308487209=82837*165673*248509
3614533077626929=84457*168913*253369
3680409480386689=84967*169933*254899
3715607011189609=85237*170473*255709
3817748810243161=86011*172021*258031
3931514590793329=86857*173713*260569
4025130566676841=87541*175081*262621
4046687647375969=87697*175393*263089
4113499616300449=88177*176353*264529
4133685643384321=88321*176641*264961
4192938532940041=88741*177481*266221
4193789079219769=88747*177493*266239
4201449172372801=88801*177601*266401
4344412864058569=89797*179593*269389
4361853161460889=89917*179833*269749
4374089100540001=90001*180001*270001
4498600676392369=90847*181693*272539
4507519919839129=90907*181813*272719
4556786561545609=91237*182473*273709
4683809578129849=92077*184153*276229
4720530528099289=92317*184633*276949
4761144691247881=92581*185161*277741
4849627431956401=93151*186301*279451
4925930867128009=93637*187273*280909
5039476248963601=94351*188701*283051
5195855080197289=95317*190633*285949
5219439659316361=95461*190921*286381
5263852900238281=95731*191461*287191
5439977476422409=96787*193573*290359
5464294563597481=96931*193861*290791
5531539974208849=97327*194653*291979
5607589831886521=97771*195541*293311
5690586528027001=98251*196501*294751
5886710601977089=99367*198733*298099
5992912792233361=99961*199921*299881
6178246534322281=100981*201961*302941
6179347884811609=100987*201973*302959
6245668701955369=101347*202693*304039
6294604390808761=101611*203221*304831
6401131330281481=102181*204361*306541
6441811333734169=102397*204793*307189
6987629665782361=105211*210421*315631
7066828790843329=105607*211213*316819
7206253022807569=106297*212593*318889
7235579644752241=106441*212881*319321
7284633973278481=106681*213361*320041
7871253109884721=109471*218941*328411
7943953907064529=109807*219613*329419
8126339234833441=110641*221281*331921
8146186349228281=110731*221461*332191
8366641458300721=111721*223441*335161
8570474936952121=112621*225241*337861
8709571271920249=113227*226453*339679
8742843679524121=113371*226741*340111
8876780691970969=113947*227893*341839
9017745727994569=114547*229093*343639
9203220800836849=115327*230653*345979
9411619439928241=116191*232381*348571
9427666858561729=116257*232513*348769
9685425749709529=117307*234613*351919
9698807445305761=117361*234721*352081
9788333868576721=117721*235441*353161
9894983109816169=118147*236293*354439
10122839733221569=119047*238093*357139
10138153312004329=119107*238213*357319
10478971179371449=120427*240853*361279
10555906290714721=120721*241441*362161
10699783088092489=121267*242533*363799
10723623830510329=121357*242713*364069
10897931091179161=122011*244021*366031
11157200671005721=122971*245941*368911
11198079276585121=123121*246241*369361
11329561583301601=123601*247201*370801
11445449444156521=124021*248041*372061
11563797396433969=124447*248893*373339
11639227434197689=124717*249433*374149
12029885538166369=126097*252193*378289
12038473772973649=126127*252253*378379
12133214278838929=126457*252913*379369
12200694240531241=126691*253381*380071
12218037003198001=126751*253501*380251
12488955217764481=127681*255361*383041
12525965420412529=127807*255613*383419
12837231302405329=128857*257713*386569
12988452966017761=129361*258721*388081
13371692604180121=130621*261241*391861
13584720828810961=131311*262621*393931
14179793373439201=133201*266401*399601
14198963801159161=133261*266521*399781
14227751827497601=133351*266701*400051
14529457281147409=134287*268573*402859
14666212790585929=134707*269413*404119
14674053203612281=134731*269461*404191
14853178330197049=135277*270553*405829
14861085229801801=135301*270601*405901
14930390332280161=135511*271021*406531
15021804274836409=135787*271573*407359
15272094696243409=136537*273073*409609
16703863920965449=140677*281353*422029
16757353669309849=140827*281653*422479
16875432811573129=141157*282313*423469
17154555468567481=141931*283861*425791
17287608624623569=142297*284593*426889
17485170180047209=142837*285673*428509
17617710556858969=143197*286393*429589
18005861759963041=144241*288481*432721
18748354957276969=146197*292393*438589
18757589803137721=146221*292441*438661
19211474955331441=147391*294781*442171
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long int
ll Eular(ll n)
{
int i;
ll ret=n;
for(i=2; i<=sqrt(n); i++)
{
if(n%i==0)
{
ret-=ret/i;
while(n%i==0) n/=i;
if(n==1) break;
}
}
if(n!=1) ret-=ret/n;
return ret;
}
int main()
{
ll n;
scanf("%lld", &n);
printf("%lld\n", Eular(n));
return 0;
}
快速版
#include<cstdio>
using namespace std;
#define ll long long int
#define N 1500001
ll phi[N];
void Eular()
{
int i, j;
phi[1]=1;
for(i=2; i<N; i++)
if(!phi[i])
for(j=i; j<N; j+=i)
{
if(!phi[j]) phi[j]=j;
phi[j]-=phi[j]/i;
}
}
int main()
{
ll n;
scanf("%lld", &n);
Eular();
printf("%lld\n", phi[n]);
return 0;
}
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 501
#define MAX ((long long)1<<61)
#define C 201
#define ll long long int
const int testnum = 8;
ll mult_mod (ll a, ll b, ll mod)
{
a%=mod;
b%=mod;
ll ans=0;
ll temp=a;
while(b)
{
if(b&1)
{
ans+=temp;
if(ans>mod)
ans-=mod;//直接取模慢很多
}
temp<<=1;
if(temp>mod)
temp-=mod;
b>>=1;
}
return ans;
}
ll pow_mod (ll a, ll n, ll mod)
{
ll ans=1;
ll temp=a%mod;
while (n)
{
if(n&1) ans=mult_mod(ans, temp, mod);
temp=mult_mod(temp, temp, mod);
n>>=1;
}
return ans;
}
bool check(ll a, ll n, ll x, ll t)
{
ll ans=pow_mod(a, x, n);
ll last=ans;
for(int i=1; i<=t; i++)
{
ans=mult_mod(ans, ans, n);
if(ans== 1 && last!=1 && last!=n-1)
return true;//合数
last=ans;
}
if(ans!=1) return true;
else return false;
}
bool Miller_Rabin (long long n)
{
if(n<2) return false;
if(n==2) return true;
if ((n&1)==0) return false;//偶数
ll x=n-1;
ll t=0;
while((x&1)==0)
{
x>>=1;
t++;
}
srand(time(NULL));
for(int i=0; i<testnum; i++)
{
ll a=rand()%(n-1)+1;
if(check(a, n, x, t))
return false;
}
return true;
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
long long n;
scanf("%lld",&n);
if(Miller_Rabin(n)) printf("Yes\n");
else printf("No\n");
}
return 0;
}
大数质因子模板：
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 501
#define MAX ((long long)1<<61)
#define C 201
#define ll long long int
const int testnum = 8;
int ct;
ll res,jl[N],num[N];
ll gcd(ll a, ll b)
{
return b? gcd(b, a%b): a;
}
ll mult_mod (ll a, ll b, ll mod)
{
a%=mod;
b%=mod;
ll ans=0;
ll temp=a;
while(b)
{
if(b&1)
{
ans+=temp;
if(ans>mod)
ans-=mod;//直接取模慢很多
}
temp<<=1;
if(temp>mod)
temp-=mod;
b>>=1;
}
return ans;
}
ll pow_mod (ll a, ll n, ll mod)
{
ll ans=1;
ll temp=a%mod;
while (n)
{
if(n&1) ans=mult_mod(ans, temp, mod);
temp=mult_mod(temp, temp, mod);
n>>=1;
}
return ans;
}
bool check(ll a, ll n, ll x, ll t)
{
ll ans=pow_mod(a, x, n);
ll last=ans;
for(int i=1; i<=t; i++)
{
ans=mult_mod(ans, ans, n);
if(ans== 1 && last!=1 && last!=n-1)
return true;//合数
last=ans;
}
if(ans!=1) return true;
else return false;
}
bool Miller_Rabin (long long n)
{
if(n<2) return false;
if(n==2) return true;
if ((n&1)==0) return false;//偶数
ll x=n-1;
ll t=0;
while((x&1)==0)
{
x>>=1;
t++;
}
srand(time(NULL));
for(int i=0; i<testnum; i++)
{
ll a=rand()%(n-1)+1;
if(check(a, n, x, t))
return false;
}
return true;
}
ll pollard_rho(ll n,int c)
{
ll x,y,d,i=1,k=2;
x=rand () % (n - 1) + 1;
y=x;
while(1)
{
i++;
x=(mult_mod(x,x,n)+c)%n;
d=gcd(y-x,n);
if(1<d&&d<n) return d;
if(y==x) return n;
if(i==k)
{
y=x;
k<<=1;
}
}
}
void find(ll n, int k)
{
if(n==1) return;
if(Miller_Rabin(n))
{
jl[ct++]=n;
if(n<res) res=n;
return;
}
ll p=n;
while(p>=n) p=pollard_rho(p,k--);
find(p,k);
find(n/p,k);
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
long long n;
scanf("%lld",&n);
res=MAX;
ct=0;
if(Miller_Rabin(n)) printf("Prime\n");
else
{
find(n,C);
sort(jl, jl+ct);
num[0]=1;
int k=1;
for(int i=1; i<ct; i++)
{
if(jl[i]==jl[i-1])
++num[k-1];
else
{
num[k]=1;
jl[k++]=jl[i];
}
}
int cnt=k;
for(int i=0; i<cnt; i++)
cout<<jl[i]<<"^"<<num[i]<<" ";
//printf("%lld\n",res);
}
}
return 0;
}
