void
eular()
{
memset(vis,
0
,
sizeof
(vis));
vis[
0
]=vis[
1
]=
1
;
for
(i=
2
;i*i<=N;i++
)
{
if
(vis[i]==
0
)
{
for
(j=i*i;j<=N;j+=
i)
vis[j]
=
1
;
}
}
//
這段求出了N內的所有素數
for
(i=
1
;i<=N;i++
)
phi[i]
=
i;
for
(i=
2
;i<=N;i++
)
{
if
(vis[i]==
0
)
{
for
(j=i;j<=N;j+=i)
//
這里從i開始，必定能整除i，其倍數也同理
phi[j]=phi[j]/i*(i-
1
);
//
此處注意先/i再*（i-1)，否則范圍較大時會溢出
}
}
}
遞歸求歐拉函數
for
(i =
1
; i <= maxn; i++) phi[i] =
i;
for
(i =
2
; i <= maxn; i +=
2
) phi[i] /=
2
;
for
(i =
3
; i <= maxn; i +=
2
)
if
(phi[i] ==
i) {
for
(j = i; j <= maxn; j +=
i)
phi[j]
= phi[j] / i * (i -
1
);
單獨求歐拉函數
unsigned euler(unsigned x)
{
//
就是公式
unsigned i, res=
x;
for
(i =
2
; i < (
int
)sqrt(x *
1.0
) +
1
; i++
)
if
(x%i==
0
)
{
res
= res / i * (i -
1
);
while
(x % i ==
0
) x /= i;
//
保證i一定是素數
}
if
(x >
1
) res = res / x * (x -
1
);
return
res;
}
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
